企业的网站建设前期工作总结,辽宁网站开发,网络营销平台,wordpress mysql php昨天晚上做的。。。差错一直查到今天 最后没办法问管理员要了数据才知道原来ans数组开小了233#xff0c;简直沙茶 这道题不就是裸的莫队嘛 ||| 只要用树状数组维护当前的两种个数即可。 1 /**************************************************************2 Problem: 3…昨天晚上做的。。。差错一直查到今天 最后没办法问管理员要了数据才知道原来ans数组开小了233简直沙茶 这道题不就是裸的莫队嘛 ||| 只要用树状数组维护当前的两种个数即可。 1 /**************************************************************2 Problem: 32363 User: rausen4 Language: C5 Result: Accepted6 Time:79318 ms7 Memory:66252 kb8 ****************************************************************/9 10 #include cstdio11 #include cmath12 #include algorithm13 14 #define lowbit(x) x -x15 using namespace std;16 const int N 100005;17 const int M 1000005;18 const int Maxlen 37000005;19 20 int n, size, Q;21 int BIT[2][N], cnt[N], pos[N], a[N];22 int ans1[M], ans2[M];23 int Len, Left;24 char buf[Maxlen];25 26 struct Query {27 int l, r, a, b, w;28 } q[M];29 inline bool operator (const Query a, const Query b) {30 return pos[a.l] pos[b.l] ? a.r b.r : pos[a.l] pos[b.l];31 }32 inline bool cmp_id (const Query a, const Query b) {33 return a.w b.w;34 }35 36 inline int read() {37 int x 0;38 while (buf[Left] 0 || 9 buf[Left])39 Left;40 while (0 buf[Left] buf[Left] 9)41 x x * 10 buf[Left] - 0;42 return x;43 }44 45 int len 0, pr[15];46 inline void print(int x) {47 while (x)48 pr[len] x % 10, x / 10;49 if (!len) putchar(0);50 while (len)51 putchar(pr[len--] 0);52 }53 54 inline void update(int x, int del, int T) {55 while (x n)56 BIT[T][x] del, x lowbit(x);57 }58 59 inline int query(int x, int T) {60 int res 0;61 while (x)62 res BIT[T][x], x - lowbit(x);63 return res;64 }65 66 inline void update(int x, int del) {67 if (!cnt[x])68 update(x, 1, 1);69 cnt[x] del;70 if (!cnt[x])71 update(x, -1, 1);72 update(x, del, 0);73 }74 75 int main() {76 int i, l, r;77 Len fread(buf, 1, Maxlen, stdin);78 buf[Len] ;79 n read(), Q read();80 size (int) sqrt(n);81 for (i 1; i n; i)82 a[i] read(), pos[i] i / size;83 for (i 1; i Q; i) {84 q[i].l read(), q[i].r read();85 q[i].a read(), q[i].b read();86 q[i].w i;87 }88 89 sort(q 1, q Q 1);90 for (i l 1, r 0; i Q; i) {91 for (; r q[i].r; ) update(a[r], 1);92 for (; r q[i].r; ) update(a[r--], -1);93 for (; l q[i].l; ) update(a[l], -1);94 for (; l q[i].l; ) update(a[--l], 1);95 ans1[q[i].w] query(q[i].b, 0) - query(q[i].a - 1, 0);96 ans2[q[i].w] query(q[i].b, 1) - query(q[i].a - 1, 1);97 }98 for (i 1; i Q; i) {99 print(ans1[i]), putchar( );
100 print(ans2[i]), putchar(\r), putchar(\n);
101 }
102 return 0;
103 } View Code p.s. 这道题Rank 1的5 sec是怎么做到的 蒟蒻可是用了80 sec啊转载于:https://www.cnblogs.com/rausen/p/4108541.html
