2019-XDU-onsite

 2020.09.02 20:10  2023.09.01 18:14  ACM  set 󰈭 585字

1427 qko的宝可梦（已补）

1428 qko的串

1429 qko的进化公式

1430 qko的树

1427 set对有序链的维护

set中每个节点拥有最小攻击力和最大攻击力，保证set中一定满足严格的偏序关系，即保证两个元素之间一定有某元素的最大值全部小于另一个元素的最小值。

初始将1号宝可梦插入到set中，然后遍历2-n宝可梦，通过lower_bound和upper_bound来获得set中“相等“的那些元素。这里的相等意味着不存在严格的偏序关系，那么也就意味着两者互相可以击败，从而这些元素都可以与第i个元素互相可达，应该合并成一个SCC。遍历所有这些相等的元素，将信息进行不断合并，最后将新元素再插入到set中，这样就可以保证set中的严格偏序关系，输出结果时将最后一个元素的个数输出即可。

算法非常精妙，由其是利用set进行合并和查询的操作值得学习！

~~原来set可以用lower/upper_bound来进行二分，之前我还在苦恼地想怎么才能在set中进行二分，orz~~

 1const int manx = 1e5 + 10;
 2
 3int a[maxn][15];
 4
 5int n, k;
 6struct NODE{
 7    int m[10], M[10], size;
 8    bool operator < (NODE const &b)const{
 9        for(int i = 0; i < k; i++) if(M[i] > b.m[i]) return 0;
10        return 1;
11    }
12}node[maxn];
13set<NODE> s;
14set<NODE>::iterator p, q, it;
15
16int main(){
17//    Fastin;
18    scanf("%d %d", &n, &k);
19    for(int i = 0; i < n; i++) for(int j = 0; j < k; j++){
20        scanf("%d", node[i].m + j); node[i].size = 1;
21        node[i].M[j] = node[i].m[j];
22    }
23    s.insert(node[0]);
24    for(int i = 1; i < n; i++){
25        NODE temp = node[i];
26        p = s.lower_bound(temp);
27        q = s.upper_bound(temp);
28        it = p;
29        while(it != q){
30            for(int i = 0; i < k; i++){
31                temp.m[i] = min(temp.m[i], it->m[i]);
32                temp.M[i] = max(temp.M[i], it->M[i]);
33            }
34            temp.size += it->size;
35            s.erase(it++);
36        }
37        s.insert(temp);
38        if(i >= 1) printf("%d\n", s.rbegin()->size);
39    }
40    return 0;
41}