c/c++语言开发共享codechef Many Lists(树状数组 set)

题意

题目链接

sol

直接做肯定不好搞(反正我不会。。)

直接开(n)个pair类型的set，维护每个数的出现位置

每次在set中二分后暴力合并即可

然后就是树状数组的基本操作了

时间复杂度：(o(nlog^2n))

#include<bits/stdc++.h> #define pair pair<int, int> #define mp make_pair #define fi first #define se second  #define lb(x) (x & (-x)) using namespace std; const int maxn = 1e5 + 10, inf = 2147483647; inline int read() {     char c = getchar(); int x = 0, f = 1;      while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n, m, t[maxn]; void add(int x, int v) {     while(x <= n) t[x] += v, x += lb(x); } void addint(int l, int r, int val) {     add(l, val); add(r + 1, -val); }  int query(int x) {     int ans = 0;     while(x) ans += t[x], x -= lb(x);     return ans; } set<pair> s[maxn]; #define sit set<pair>::iterator  void add(int l, int r, int x) {     set<pair> &s = s[x];      //printf("%dn", s.size());     sit it = s.lower_bound(mp(l, r));     if(it != s.begin()) it--; //  printf("%d %dn", it -> fi, it -> se);     while((it -> se >= l && it -> se <= r) || (it -> fi >= l && it -> se <= r)) {         printf("%d %dn", it -> fi, it -> se);         l = min(l, it -> fi); r = max(r, it -> se);         addint(it -> fi, it -> se, -1);         s.erase(it);     }     s.insert(mp(l, r));     addint(l, r, 1); } int main() {     n = read(); m = read();     for(int i = 1; i <= n; i++) s[i].insert(mp(inf, inf));      while(m--) {         int opt = read();         if(opt == 0) {int l = read(), r = read(), val = read(); add(l, r, val);}         else printf("%dn", query(read()));     }     return 0; } /* 5 5 0 2 4 4 0 3 5 5 0 1 5 5 1 5 1 3 */