Description:
Input:
Output:
Sample Input:
1 2 3 4 5 6 | 3 4 1 2 2 1 2 1 3 1 2 1 1 1 3 1 3 2 3 2 3 |
Sample Output:
1 2 3 4 | 2 2 1 1 3 2 2 1 |
HINT:
N=100000,M=1000000
题解:
在某处看到的二维数点的例题,然后就去想主席树,想扫描线加线段树什么的。
结果这是个莫队+树状数组的题。。
它在检测我二维数点有没有学傻???
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | /* ID: Sunshine_cfbsl PROG: BZOJ3236 LANG: C++ */ #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int MAXN = 100010; const int MAXM = 1000010; const int Base = 200; int n, m, C[2][MAXN], cnt; int c[MAXN], Hash[MAXN]; int a[MAXN], in[MAXN], L, R; int ans1[MAXM], ans2[MAXM]; struct Query { int l, r, a, b, ord; bool operator < (const Query &rhs) const { if(in[l] != in[rhs.l]) return in[l] < in[rhs.l]; return r > rhs.r; } }q[MAXM]; inline int read() { int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch=='-') ch = getchar(); for(; isdigit(ch); ch = getchar()) x = (x<<1)+(x<<3)+(ch^48); return x * f; } inline int find(int x) { return lower_bound(Hash+1, Hash+cnt+1, x)-Hash; } inline int lowbit(int x) { return x & (-x); } inline void Add(int t, int x, int p) { while(x <= cnt) { C[t][x] += p; x += lowbit(x); } } inline int Query(int t, int x) { int res = 0; while(x) { res += C[t][x]; x -= lowbit(x); } return res; } inline int query(int t, int l, int r) { return Query(t, r)-Query(t, l-1); } int main() { int i; scanf("%d%d", &n, &m); for(i = 1; i <= n; i++) Hash[++cnt] = a[i] = read(); sort(Hash+1, Hash+cnt+1); cnt = unique(Hash+1, Hash+cnt+1)-Hash-1; for(i = 1; i <= n; i++) a[i] = find(a[i]); for(i = 1; i <= n; i++) in[i] = (i-1)/Base+1; for(i = 1; i <= m; i++) { int x; q[i].l = read(), q[i].r = read(); q[i].a = find(read()), q[i].b = find(x = read()); if(Hash[q[i].b] != x) q[i].b--; q[i].ord = i; } sort(q+1, q+m+1); L = 1, R = 0; for(i = 1; i <= m; i++) { while(R < q[i].r) { Add(0, a[++R], 1); if(c[a[R]] == 0) Add(1, a[R], 1); c[a[R]]++; } while(R > q[i].r) { Add(0, a[R], -1); if(c[a[R]] == 1) Add(1, a[R], -1); c[a[R--]]--; } while(L < q[i].l) { Add(0, a[L], -1); if(c[a[L]] == 1) Add(1, a[L], -1); c[a[L++]]--; } while(L > q[i].l) { Add(0, a[--L], 1); if(c[a[L]] == 0) Add(1, a[L], 1); c[a[L]]++; } if(q[i].a > q[i].b) { ans1[q[i].ord] = ans2[q[i].ord] = 0; continue; } ans1[q[i].ord] = query(0, q[i].a, q[i].b); ans2[q[i].ord] = query(1, q[i].a, q[i].b); } for(i = 1; i <= m; i++) printf("%d %d\n", ans1[i], ans2[i]); return 0; } |