冲着这个智慧的数字"⑨"就值得一写。
T1，区间加，单点查。
打个标记就行了。
1 #include2 #include 3 4 const int N = 50010; 5 6 int le[N], re[N], sum[N], tag[N], a[N], fr[N]; 7 8 inline void add(int x, int y, int c) { 9 int l = fr[x], r = fr[y];10 if(l == r) {11 for(int i = x; i <= y; i++) {12 a[i] += c;13 sum[r] += c;14 }15 return;16 }17 for(int i = l + 1; i < r; i++) {18 sum[i] += c * (re[i] - le[i] + 1);19 tag[i] += c;20 }21 for(int i = x; i <= re[l]; i++) {22 a[i] += c;23 sum[l] += c;24 }25 for(int i = le[r]; i <= y; i++) {26 a[i] += c;27 sum[r] += c;28 }29 return;30 }31 32 inline int ask(int x) {33 return a[x] + tag[fr[x]];34 }35 36 int main() {37 int n;38 scanf("%d", &n);39 for(int i = 1; i <= n; i++) {40 scanf("%d", &a[i]);41 }42 int T = sqrt(n);43 for(int i = 1; i <= T; i++) {44 le[i] = T * (i - 1) + 1;45 re[i] = T * i;46 for(int j = le[i]; j <= re[i]; j++) {47 fr[j] = i;48 sum[i] += a[j];49 }50 }51 if(re[T] < n) {52 T++;53 le[T] = re[T - 1] + 1;54 re[T] = n;55 for(int i = le[T]; i <= n; i++) {56 sum[T] += a[i];57 fr[i] = T;58 }59 }60 61 for(int i = 1, f, x, y, z; i <= n; i++) {62 scanf("%d%d%d%d", &f, &x, &y, &z);63 if(f == 0) {64 add(x, y, z);65 }66 else {67 int t = ask(y);68 printf("%d\n", t);69 }70 }71 72 return 0;73 }
T2，区间加，询问区间比x大的数的个数。
yy了一个n1.5logn的做法，然后发现复杂度可过......
有一个SB错误害我调了半天：931每块大小是30，这样就会有32块，最后要加上两块，而我只加了一块。
好像有高端写法可以避免...下一题试一下。
1 #include2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 50010; 7 8 LL a[N], tag[N], p[2000][2000]; 9 int fr[N], le[N], re[N]; 10 11 inline void add(int x, int y, LL c) { 12 int l = fr[x], r = fr[y]; 13 if(l == r) { 14 for(int i = x; i <= y; i++) { 15 a[i] += c; 16 } 17 p[r][0] = 0; 18 for(int i = le[r]; i <= re[r]; i++) { 19 p[r][++p[r][0]] = a[i]; 20 } 21 std::sort(p[r] + 1, p[r] + p[r][0] + 1); 22 return; 23 } 24 for(int i = l + 1; i < r; i++) { 25 tag[i] += c; 26 } 27 for(int i = x; i <= re[l]; i++) { 28 a[i] += c; 29 } 30 p[l][0] = 0; 31 for(int i = le[l]; i <= re[l]; i++) { 32 p[l][++p[l][0]] = a[i]; 33 } 34 std::sort(p[l] + 1, p[l] + p[l][0] + 1); 35 for(int i = le[r]; i <= y; i++) { 36 a[i] += c; 37 } 38 p[r][0] = 0; 39 for(int i = le[r]; i <= re[r]; i++) { 40 p[r][++p[r][0]] = a[i]; 41 } 42 std::sort(p[r] + 1, p[r] + p[r][0] + 1); 43 return; 44 } 45 46 inline int ask(int x, int y, LL c) { 47 int l = fr[x], r = fr[y], ans = 0; 48 if(l == r) { 49 for(int i = x; i <= y; i++) { 50 ans += (a[i] + tag[r] < c); 51 } 52 return ans; 53 } 54 for(int i = l + 1; i < r; i++) { 55 int t = std::lower_bound(p[i] + 1, p[i] + p[i][0] + 1, c - tag[i]) - p[i]; 56 ans += t - 1; 57 } 58 for(int i = x; i <= re[l]; i++) { 59 ans += (a[i] + tag[l] < c); 60 } 61 for(int i = le[r]; i <= y; i++) { 62 ans += (a[i] + tag[r] < c); 63 } 64 return ans; 65 } 66 67 int main() { 68 69 int n; 70 scanf("%d", &n); 71 int T = sqrt(n); 72 for(int i = 1; i <= n; i++) { 73 scanf("%lld", &a[i]); 74 fr[i] = (i - 1) / T + 1; 75 p[fr[i]][++p[fr[i]][0]] = a[i]; 76 } 77 for(int i = 1; i <= T; i++) { 78 le[i] = (i - 1) * T + 1; 79 re[i] = i * T; 80 std::sort(p[i] + 1, p[i] + p[i][0] + 1); 81 } 82 while(re[T] < n) { 83 T++; 84 re[T] = std::min(n, T * re[1]); 85 le[T] = re[T - 1] + 1; 86 std::sort(p[T] + 1, p[T] + p[T][0] + 1); 87 } 88 89 LL z; 90 for(int i = 1, f, x, y; i <= n; i++) { 91 scanf("%d%d%d%lld", &f, &x, &y, &z); 92 if(f == 0) { 93 add(x, y, z); 94 } 95 else { 96 int t = ask(x, y, z * z); 97 printf("%d\n", t); 98 } 99 }100 101 return 0;102 }
T3，区间加，询问区间前驱。
其实跟T2差别不大...数据范围开到100000了。感觉过不去，加了点剪枝，最后还是过了...
剪枝就是记录区间max，min。如果max < c 或 min > c就可以直接判断。
1 #include2 #include 3 #include 4 #include 5 6 const int N = 100010, INF = LONG_MAX; 7 8 inline void read(int &x) { 9 x = 0; 10 char c = getchar(); 11 bool f = 0; 12 while(c < '0' || c > '9') { 13 if(c == '-') { 14 f = 1; 15 } 16 c = getchar(); 17 } 18 while(c >= '0' && c <= '9') { 19 x = (x << 3) + (x << 1) + c - 48; 20 c = getchar(); 21 } 22 if(f) { 23 x = (~x) + 1; 24 } 25 return; 26 } 27 28 int a[N], tag[N], large[N], small[N], fr[N], le[N], re[N]; 29 int p[350][350]; 30 31 inline void update(int x) { 32 large[x] = -INF - 1; 33 small[x] = INF; 34 p[x][0] = 0; 35 for(int i = le[x]; i <= re[x]; i++) { 36 p[x][++p[x][0]] = a[i]; 37 large[x] = std::max(large[x], a[i]); 38 small[x] = std::min(small[x], a[i]); 39 } 40 std::sort(p[x] + 1, p[x] + p[x][0] + 1); 41 return; 42 } 43 44 inline void add(int x, int y, int c) { 45 int l = fr[x], r = fr[y]; 46 if(l == r) { 47 for(int i = x; i <= y; i++) { 48 a[i] += c; 49 } 50 update(r); 51 return; 52 } 53 for(int i = l + 1; i < r; i++) { 54 tag[i] += c; 55 } 56 for(int i = x; i <= re[l]; i++) { 57 a[i] += c; 58 } 59 update(l); 60 for(int i = le[r]; i <= y; i++) { 61 a[i] += c; 62 } 63 update(r); 64 return; 65 } 66 67 inline int ask(int x, int y, int c) { 68 int ans = -1, l = fr[x], r = fr[y]; 69 if(l == r) { 70 if(small[r] + tag[r] >= c) { 71 return -1; 72 } 73 for(int i = x; i <= y; i++) { 74 if(a[i] + tag[r] < c) { 75 ans = std::max(ans, a[i] + tag[r]); 76 } 77 } 78 return ans; 79 } 80 for(int i = l + 1; i < r; i++) { 81 if(large[i] + tag[i] < c) { 82 ans = std::max(ans, large[i] + tag[i]); 83 continue; 84 } 85 if(small[i] + tag[i] >= c) { 86 continue; 87 } 88 int t = std::lower_bound(p[i] + 1, p[i] + p[i][0] + 1, c - tag[i]) - p[i]; 89 if(t > 1) { 90 ans = std::max(ans, p[i][t - 1] + tag[i]); 91 } 92 } 93 for(int i = x; i <= re[l] && small[l] + tag[l] < c; i++) { 94 if(a[i] + tag[l] < c) { 95 ans = std::max(ans, a[i] + tag[l]); 96 } 97 } 98 for(int i = le[r]; i <= y && small[r] + tag[r] < c; i++) { 99 if(a[i] + tag[r] < c) {100 ans = std::max(ans, a[i] + tag[r]);101 }102 }103 return ans;104 }105 106 int main() {107 int n;108 read(n);109 int T = sqrt(n);110 for(int i = 1; i <= n; i++) {111 read(a[i]);112 fr[i] = (i - 1) / T + 1;113 }114 for(int i = 1; i <= fr[n]; i++) {115 le[i] = (i - 1) * T + 1;116 re[i] = i * T;117 if(i == fr[n]) {118 re[i] = n;119 }120 update(i);121 }122 123 for(int i = 1, f, x, y, z; i <= n; i++) {124 read(f);125 read(x);126 read(y);127 read(z);128 if(f == 0) {129 add(x, y, z);130 }131 else {132 int t = ask(x, y, z);133 printf("%d\n", t);134 }135 }136 137 return 0;138 }
T4，区间加，区间求和。
打个标记就行了...
1 #include2 #include 3 4 typedef long long LL; 5 const int N = 100010; 6 7 int le[N], re[N], fr[N]; 8 LL a[N], tag[N], sum[N]; 9 10 inline void add(int x, int y, LL c) {11 int l = fr[x], r = fr[y];12 if(l == r) {13 for(int i = x; i <= y; i++) {14 a[i] += c;15 sum[r] += c;16 }17 return;18 }19 for(int i = l + 1; i < r; i++) {20 tag[i] += c;21 sum[i] += c * (re[i] - le[i] + 1);22 }23 for(int i = x; i <= re[l]; i++) {24 a[i] += c;25 sum[l] += c;26 }27 for(int i = le[r]; i <= y; i++) {28 a[i] += c;29 sum[r] += c;30 }31 return;32 }33 34 inline LL ask(int x, int y) {35 int l = fr[x], r = fr[y];36 LL ans = 0;37 if(l == r) {38 for(int i = x; i <= y; i++) {39 ans += a[i] + tag[r];40 }41 return ans;42 }43 for(int i = l + 1; i < r; i++) {44 ans += sum[i];45 }46 for(int i = x; i <= re[l]; i++) {47 ans += a[i] + tag[l];48 }49 for(int i = le[r]; i <= y; i++) {50 ans += a[i] + tag[r];51 }52 return ans;53 }54 55 int main() {56 int n;57 scanf("%d", &n);58 int T = sqrt(n);59 for(int i = 1; i <= n; i++) {60 scanf("%lld", &a[i]);61 fr[i] = (i - 1) / T + 1;62 sum[fr[i]] += a[i];63 }64 for(int i = 1; i <= fr[n]; i++) {65 le[i] = re[i - 1] + 1;66 re[i] = le[i] + T - 1;67 if(i == fr[n]) {68 re[i] = n;69 }70 }71 72 LL z;73 for(int i = 1, x, y, f; i <= n; i++) {74 scanf("%d%d%d%lld", &f, &x, &y, &z);75 if(f == 0) {76 add(x, y, z);77 }78 else {79 LL t = ask(x, y) % (z + 1);80 printf("%lld\n", t);81 }82 }83 84 return 0;85 }
T5，区间开方下取整，区间求和。
跟一样，维护最大值即可。
1 #include2 #include 3 #include 4 5 const int N = 50010; 6 7 int fr[N], le[N], re[N], sum[N], large[N], a[N]; 8 9 inline void update(int x) { 10 sum[x] = large[x] = 0; 11 for(int i = le[x]; i <= re[x]; i++) { 12 sum[x] += a[i]; 13 large[x] = std::max(large[x], a[i]); 14 } 15 return; 16 } 17 18 inline void change(int x, int y) { 19 int l = fr[x], r = fr[y]; 20 if(l == r) { 21 if(large[r] <= 1) { 22 return; 23 } 24 for(int i = x; i <= y; i++) { 25 if(a[i] > 1) { 26 a[i] = sqrt(a[i]); 27 } 28 } 29 update(r); 30 return; 31 } 32 for(int i = l + 1; i < r; i++) { 33 if(large[i] <= 1) { 34 continue; 35 } 36 for(int j = le[i]; j <= re[i]; j++) { 37 if(a[j] > 1) { 38 a[j] = sqrt(a[j]); 39 } 40 } 41 update(i); 42 } 43 if(large[l] > 1) { 44 for(int i = x; i <= re[l]; i++) { 45 if(a[i] > 1) { 46 a[i] = sqrt(a[i]); 47 } 48 } 49 update(l); 50 } 51 if(large[r] > 1) { 52 for(int i = le[r]; i <= y; i++) { 53 if(a[i] > 1) { 54 a[i] = sqrt(a[i]); 55 } 56 } 57 update(r); 58 } 59 return; 60 } 61 62 inline int ask(int x, int y) { 63 int l = fr[x], r = fr[y], ans = 0; 64 if(l == r) { 65 for(int i = x; i <= y; i++) { 66 ans += a[i]; 67 } 68 return ans; 69 } 70 for(int i = l + 1; i < r; i++) { 71 ans += sum[i]; 72 } 73 for(int i = x; i <= re[l]; i++) { 74 ans += a[i]; 75 } 76 for(int i = le[r]; i <= y; i++) { 77 ans += a[i]; 78 } 79 return ans; 80 } 81 82 int main() { 83 int n; 84 scanf("%d", &n); 85 int T = sqrt(n); 86 for(int i = 1; i <= n; i++) { 87 scanf("%d", &a[i]); 88 fr[i] = (i - 1) / T + 1; 89 } 90 for(int i = 1; i <= fr[n]; i++) { 91 le[i] = re[i - 1] + 1; 92 re[i] = le[i] + T - 1; 93 if(i == fr[n]) { 94 re[i] = n; 95 } 96 update(i); 97 } 98 99 for(int i = 1, f, x, y, z; i <= n; i++) {100 scanf("%d%d%d%d", &f, &x, &y, &z);101 if(f == 0) {102 change(x, y);103 }104 else {105 int t = ask(x, y);106 printf("%d\n", t);107 }108 }109 110 return 0;111 }
第一个一次写对的分块...感动啊。
T7，区间加，乘，单点查值。
感觉这个顺序比较自然就先写7了...
跟线段树一样打两个标记即可。这个还不用记sum。
1 #include2 #include 3 4 const int N = 100010, MO = 10007; 5 6 int a[N], tagm[N], taga[N]; 7 int fr[N], le[N], re[N]; 8 9 inline void pushdown(int x) { 10 if(tagm[x] != 1) { 11 for(int i = le[x]; i <= re[x]; i++) { 12 (a[i] *= tagm[x]) %= MO; 13 } 14 tagm[x] = 1; 15 } 16 if(taga[x] != 0) { 17 for(int i = le[x]; i <= re[x]; i++) { 18 (a[i] += taga[x]) %= MO; 19 } 20 taga[x] = 0; 21 } 22 return; 23 } 24 25 inline void add(int x, int y, int c) { 26 int l = fr[x], r = fr[y]; 27 if(l == r) { 28 pushdown(r); 29 for(int i = x; i <= y; i++) { 30 (a[i] += c) %= MO; 31 } 32 return; 33 } 34 for(int i = l + 1; i < r; i++) { 35 (taga[i] += c) %= MO; 36 } 37 pushdown(l); 38 for(int i = x; i <= re[l]; i++) { 39 (a[i] += c) %= MO; 40 } 41 pushdown(r); 42 for(int i = le[r]; i <= y; i++) { 43 (a[i] += c) %= MO; 44 } 45 return; 46 } 47 48 inline void mul(int x, int y, int c) { 49 int l = fr[x], r = fr[y]; 50 if(l == r) { 51 pushdown(r); 52 for(int i = x; i <= y; i++) { 53 (a[i] *= c) %= MO; 54 } 55 return; 56 } 57 for(int i = l + 1; i < r; i++) { 58 (tagm[i] *= c) %= MO; 59 (taga[i] *= c) %= MO; 60 } 61 pushdown(l); 62 for(int i = x; i <= re[l]; i++) { 63 (a[i] *= c) %= MO; 64 } 65 pushdown(r); 66 for(int i = le[r]; i <= y; i++) { 67 (a[i] *= c) %= MO; 68 } 69 return; 70 } 71 72 inline int ask(int x) { 73 return (a[x] * tagm[fr[x]] % MO + taga[fr[x]]) % MO; 74 } 75 76 int main() { 77 int n; 78 scanf("%d", &n); 79 int T = sqrt(n); 80 for(int i = 1; i <= n; i++) { 81 scanf("%d", &a[i]); 82 a[i] %= MO; 83 fr[i] = (i - 1) / T + 1; 84 } 85 for(int i = 1; i <= fr[n]; i++) { 86 le[i] = re[i - 1] + 1; 87 re[i] = le[i] + T - 1; 88 if(i == fr[n]) { 89 re[i] = n; 90 } 91 tagm[i] = 1; 92 } 93 94 for(int i = 1, f, x, y, z; i <= n; i++) { 95 scanf("%d%d%d%d", &f, &x, &y, &z); 96 if(!f) { 97 add(x, y, z % MO); 98 } 99 else if(f == 1) {100 mul(x, y, z % MO);101 }102 else {103 int t = ask(y);104 printf("%d\n", t);105 }106 }107 108 return 0;109 }
T8，区间查询等于c的数的个数，并全部改为c。
又是玄学题目...复杂度懒得证了。
维护一个每段是否相同的标记。
1 #include2 #include 3 4 const int N = 100010; 5 6 int a[N], vis[N], tag[N]; 7 int fr[N], le[N], re[N]; 8 9 inline void solve(int x, int y, int c) { 10 int l = fr[x], r = fr[y], ans = 0; 11 if(l == r) { 12 if(vis[r] && tag[r] == c) { 13 printf("%d\n", y - x + 1); 14 return; 15 } 16 else if(vis[r]) { 17 vis[r] = 0; 18 for(int i = le[r]; i <= re[r]; i++) { 19 if(x <= i && i <= y) { 20 a[i] = c; 21 } 22 else { 23 a[i] = tag[r]; 24 } 25 } 26 puts("0"); 27 return; 28 } 29 for(int i = x; i <= y; i++) { 30 ans += (a[i] == c); 31 a[i] = c; 32 } 33 printf("%d\n", ans); 34 return; 35 } 36 for(int i = l + 1; i < r; i++) { 37 if(vis[i]) { 38 ans += (tag[i] == c) * (re[i] - le[i] + 1); 39 tag[i] = c; 40 } 41 else { 42 vis[i] = 1; 43 tag[i] = c; 44 for(int j = le[i]; j <= re[i]; j++) { 45 ans += (a[j] == c); 46 } 47 } 48 } 49 if(vis[l] && tag[l] == c) { 50 ans += (re[l] - x + 1); 51 } 52 else if(vis[l]) { 53 vis[l] = 0; 54 for(int i = le[l]; i < x; i++) { 55 a[i] = tag[l]; 56 } 57 for(int i = x; i <= re[l]; i++) { 58 a[i] = c; 59 } 60 } 61 else { 62 for(int i = x; i <= re[l]; i++) { 63 ans += (a[i] == c); 64 a[i] = c; 65 } 66 } 67 68 if(vis[r] && tag[r] == c) { 69 ans += (y - le[r] + 1); 70 } 71 else if(vis[r]) { 72 vis[r] = 0; 73 for(int i = le[r]; i <= y; i++) { 74 a[i] = c; 75 } 76 for(int i = y + 1; i <= re[r]; i++) { 77 a[i] = tag[r]; 78 } 79 } 80 else { 81 for(int i = le[r]; i <= y; i++) { 82 ans += (a[i] == c); 83 a[i] = c; 84 } 85 } 86 printf("%d\n", ans); 87 return; 88 } 89 90 int main() { 91 int n; 92 scanf("%d", &n); 93 int T = sqrt(n); 94 for(int i = 1; i <= n; i++) { 95 scanf("%d", &a[i]); 96 fr[i] = (i - 1) / T + 1; 97 } 98 for(int i = 1; i <= fr[n]; i++) { 99 le[i] = re[i - 1] + 1;100 re[i] = le[i] + T - 1;101 if(i == fr[n]) {102 re[i] = n;103 }104 }105 106 for(int i = 1, x, y, z; i <= n; i++) {107 scanf("%d%d%d", &x, &y, &z);108 solve(x, y, z);109 }110 111 return 0;112 }
T9，静态区间众数。
这道题可以用三种方法，两种在线一种离线。
离线是莫队套值域线段树，维护出现次数最大值，复杂度O(n1.5logn)，可能需要卡常......
好像可以做到n√n...开两个桶，第一个维护出现次数，第二个维护出现次数为i的有几个数。
在线：
有一个共通的就是，需要预处理出块两两之间的众数。
然后对于某询问，答案要么是块(l, r)之间的众数，要么是在两边出现的数。
枚举两边出现的数，这不超过2n0.5个，然后对于每个数查询出现次数即可。
①：
处理出sum[i][j]表示前i块中j出现的次数。
查询时用n0.5的时间调整附近两块的sum到查询区间的sum，然后可以做到O(1)查询。之后再还原。
预处理：块i，j之间的众数，要么是块i，j - 1的众数，要么是第j块中的数。枚举查询即可。
时间复杂度：O(n1.5 + n1.5)，空间复杂度：O(n1.5)
1 #include2 #include 3 #include 4 5 const int N = 100010; 6 7 int a[N], sum[350][N], X[N], fr[N], le[N], re[N], md[350][350]; 8 9 inline int ask(int x, int y) { 10 int l = fr[x], r = fr[y]; 11 int ans = md[l + 1][r - 1]; 12 if(l == r) { 13 for(int i = le[l]; i < x; i++) { 14 sum[l - 1][a[i]]++; 15 } 16 for(int i = y + 1; i <= re[r]; i++) { 17 sum[r][a[i]]--; 18 } 19 // 20 for(int i = x; i <= y; i++) { 21 if(sum[r][a[i]] - sum[l - 1][a[i]] > sum[r][ans] - sum[l - 1][ans]) { 22 ans = a[i]; 23 } 24 else if(sum[r][a[i]] - sum[l - 1][a[i]] == sum[r][ans] - sum[l - 1][ans]) { 25 ans = std::min(ans, a[i]); 26 } 27 } 28 // 29 for(int i = le[l]; i < x; i++) { 30 sum[l - 1][a[i]]--; 31 } 32 for(int i = y + 1; i <= re[r]; i++) { 33 sum[r][a[i]]++; 34 } 35 return ans; 36 } 37 for(int i = le[l]; i < x; i++) { 38 sum[l - 1][a[i]]++; 39 } 40 for(int i = y + 1; i <= re[r]; i++) { 41 sum[r][a[i]]--; 42 } 43 // 44 for(int i = x; i <= re[l]; i++) { 45 if(sum[r][a[i]] - sum[l - 1][a[i]] > sum[r][ans] - sum[l - 1][ans]) { 46 ans = a[i]; 47 } 48 else if(sum[r][a[i]] - sum[l - 1][a[i]] == sum[r][ans] - sum[l - 1][ans]) { 49 ans = std::min(ans, a[i]); 50 } 51 } 52 for(int i = le[r]; i <= y; i++) { 53 if(sum[r][a[i]] - sum[l - 1][a[i]] > sum[r][ans] - sum[l - 1][ans]) { 54 ans = a[i]; 55 } 56 else if(sum[r][a[i]] - sum[l - 1][a[i]] == sum[r][ans] - sum[l - 1][ans]) { 57 ans = std::min(ans, a[i]); 58 } 59 } 60 // 61 for(int i = le[l]; i < x; i++) { 62 sum[l - 1][a[i]]--; 63 } 64 for(int i = y + 1; i <= re[r]; i++) { 65 sum[r][a[i]]++; 66 } 67 return ans; 68 } 69 70 int main() { 71 int n; 72 scanf("%d", &n); 73 int T = sqrt(n); 74 for(int i = 1; i <= n; i++) { 75 scanf("%d", &a[i]); 76 fr[i] = (i - 1) / T + 1; 77 X[i] = a[i]; 78 } 79 std::sort(X + 1, X + n + 1); 80 int temp = std::unique(X + 1, X + n + 1) - X - 1; 81 for(int i = 1; i <= fr[n]; i++) { 82 le[i] = re[i - 1] + 1; 83 re[i] = le[i] + T - 1; 84 if(i == fr[n]) { 85 re[i] = n; 86 } 87 } 88 for(int i = 1; i <= n; i++) { 89 a[i] = std::lower_bound(X + 1, X + temp + 1, a[i]) - X; 90 sum[fr[i]][a[i]]++; 91 } 92 for(int i = 1; i <= fr[n]; i++) { 93 for(int j = 1; j <= temp; j++) { 94 sum[i][j] += sum[i - 1][j]; 95 } 96 } 97 for(int l = 1; l <= fr[n]; l++) { 98 for(int r = l; r <= fr[n]; r++) { 99 // md l r100 md[l][r] = md[l][r - 1];101 for(int i = le[r]; i <= re[r]; i++) {102 // md[l][r] a[i]103 if(sum[r][a[i]] - sum[l - 1][a[i]] > sum[r][md[l][r]] - sum[l - 1][md[l][r]]) {104 md[l][r] = a[i];105 }106 else if(sum[r][a[i]] - sum[l - 1][a[i]] == sum[r][md[l][r]] - sum[l - 1][md[l][r]]) {107 md[l][r] = std::min(md[l][r], a[i]);108 }109 }110 }111 }112 113 for(int i = 1, x, y; i <= n; i++) {114 scanf("%d%d", &x, &y);115 int t = ask(x, y);116 printf("%d\n", X[t]);117 }118 119 return 0;120 }
②：实测TLE，但是思路值得借鉴：
使用n个vector，v[i]表示i出现的下标。
查询的时候在对应vector里面二分左右边界的下标，然后相减，就是出现次数。
1 #include2 #include 3 #include 4 #include 5 6 const int N = 40010; 7 8 int a[N], fr[N], le[N], re[N], md[250][250], X[N]; 9 std::vector v[N]; 10 11 inline int cnt(int x, int y, int c) { 12 x = std::lower_bound(v[c].begin(), v[c].end(), x) - v[c].begin(); 13 y = std::upper_bound(v[c].begin(), v[c].end(), y) - v[c].begin(); 14 // [x, y) 15 return y - x; 16 } 17 18 inline int ask(int x, int y) { 19 int l = fr[x], r = fr[y]; 20 int ans = md[l + 1][r - 1]; 21 int large = cnt(x, y, ans); 22 if(l == r) { 23 for(int i = x; i <= y; i++) { 24 int A = cnt(x, y, a[i]); 25 if(A > large) { 26 large = A; 27 ans = a[i]; 28 } 29 else if(A == large) { 30 ans = std::min(ans, a[i]); 31 } 32 } 33 return ans; 34 } 35 for(int i = x; i <= re[l]; i++) { 36 int A = cnt(x, y, a[i]); 37 if(A > large) { 38 large = A; 39 ans = a[i]; 40 } 41 else if(A == large) { 42 ans = std::min(ans, a[i]); 43 } 44 } 45 for(int i = le[r]; i <= y; i++) { 46 int A = cnt(x, y, a[i]); 47 if(A > large) { 48 large = A; 49 ans = a[i]; 50 } 51 else if(A == large) { 52 ans = std::min(ans, a[i]); 53 } 54 } 55 return ans; 56 } 57 58 int main() { 59 int n; 60 scanf("%d", &n); 61 int T = sqrt(n); 62 for(int i = 1; i <= n; i++) { 63 scanf("%d", &a[i]); 64 fr[i] = (i - 1) / T + 1; 65 X[i] = a[i]; 66 } 67 for(int i = 1; i <= fr[n]; i++) { 68 le[i] = re[i - 1] + 1; 69 re[i] = le[i] + T - 1; 70 if(i == fr[n]) { 71 re[i] = n; 72 } 73 } 74 std::sort(X + 1, X + n + 1); 75 int temp = std::unique(X + 1, X + n + 1) - X - 1; 76 for(int i = 1; i <= n; i++) { 77 a[i] = std::lower_bound(X + 1, X + temp + 1, a[i]) - X; 78 v[a[i]].push_back(i); 79 } 80 for(int i = 1; i <= temp; i++) { 81 std::sort(v[i].begin(), v[i].end()); 82 } 83 for(int l = 1; l <= fr[n]; l++) { 84 for(int r = l; r <= fr[n]; r++) { 85 md[l][r] = md[l][r - 1]; 86 int large = cnt(le[l], re[r], md[l][r]); 87 for(int i = le[r]; i <= re[r]; i++) { 88 int A = cnt(le[l], re[r], a[i]); 89 if(A > large) { 90 md[l][r] = a[i]; 91 large = A; 92 } 93 else if(A == large) { 94 md[l][r] = std::min(md[l][r], a[i]); 95 } 96 } 97 } 98 } 99 100 for(int i = 1, x, y; i <= n; i++) {101 scanf("%d%d", &x, &y);102 int t = ask(x, y);103 printf("%d\n", X[t]);104 }105 106 return 0;107 }
还有带修区间众数...没找到啥题，算了。真的遇到就直接上n²好了。
可以带修莫队套值域线段树，n5/3logn跟n²也差不了多少了...50000的复杂度是10亿呢。
有一种n1.5logn的做法，懒得学了...
T6，单点插入，单点求值。
块状链表，学鬼啊，直接splay水过去算了。
1 #include2 #include 3 4 const int N = 2000010; 5 6 int fa[N], s[N][2], val[N], S[N], Sp, siz[N], root, tot, A[N]; 7 bool rev[N]; 8 9 inline void pushup(int x) { 10 siz[x] = siz[s[x][0]] + siz[s[x][1]] + 1; 11 if(!fa[x]) { 12 root = x; 13 } 14 return; 15 } 16 17 inline void pushdown(int x) { 18 if(rev[x]) { 19 if(s[x][0]) { 20 rev[s[x][0]] ^= 1; 21 } 22 if(s[x][1]) { 23 rev[s[x][1]] ^= 1; 24 } 25 std::swap(s[x][0], s[x][1]); 26 rev[x] = 0; 27 } 28 return; 29 } 30 31 inline void rotate(int x) { 32 int y = fa[x]; 33 int z = fa[y]; 34 bool f = (s[y][1] == x); 35 36 fa[x] = z; 37 if(z) { 38 s[z][s[z][1] == y] = x; 39 } 40 s[y][f] = s[x][!f]; 41 if(s[x][!f]) { 42 fa[s[x][!f]] = y; 43 } 44 s[x][!f] = y; 45 fa[y] = x; 46 47 pushup(y); 48 pushup(x); 49 return; 50 } 51 52 inline void splay(int x, int g = 0) { 53 int y = x; 54 S[++Sp] = y; 55 while(fa[y]) { 56 y = fa[y]; 57 S[++Sp] = y; 58 } 59 while(Sp) { 60 pushdown(S[Sp]); 61 Sp--; 62 } 63 64 y = fa[x]; 65 int z = fa[y]; 66 while(y != g) { 67 if(z != g) { 68 (s[z][1] == y) ^ (s[y][1] == x) ? 69 rotate(x) : rotate(y); 70 } 71 rotate(x); 72 y = fa[x]; 73 z = fa[y]; 74 } 75 return; 76 } 77 78 inline int np(int x, int f) { 79 ++tot; 80 val[tot] = x; 81 fa[tot] = f; 82 pushup(tot); 83 return tot; 84 } 85 86 int build(int l, int r, int f) { 87 int mid = (l + r) >> 1; 88 int p = np(A[mid], f); 89 if(l < mid) { 90 s[p][0] = build(l, mid - 1, p); 91 } 92 if(mid < r) { 93 s[p][1] = build(mid + 1, r, p); 94 } 95 pushup(p); 96 return p; 97 } 98 99 void out(int x) {100 if(s[x][0]) {101 out(s[x][0]);102 }103 printf("%d", val[x]);104 if(s[x][1]) {105 out(s[x][1]);106 }107 return;108 }109 110 inline int getPbyR(int k) {111 int p = root;112 while(1) {113 pushdown(p);114 if(siz[s[p][0]] >= k) {115 p = s[p][0];116 }117 else if(siz[s[p][0]] + 1 == k) {118 break;119 }120 else {121 k -= (siz[s[p][0]] + 1);122 p = s[p][1];123 }124 }125 splay(p);126 return p;127 }128 129 inline int getRP() {130 pushdown(root);131 int p = s[root][1];132 pushdown(p);133 while(s[p][0]) {134 p = s[p][0];135 pushdown(p);136 }137 return p;138 }139 140 inline void insert(int k, int c) { // after k insert c141 int y = getPbyR(k + 1);142 int x = getRP();143 splay(x, y);144 s[x][0] = build(1, c, x);145 pushup(x);146 pushup(y);147 return;148 }149 150 inline void ask(int l, int r) {151 int x = getPbyR(l);152 int y = getPbyR(r + 2);153 splay(x, y);154 out(s[x][1]);155 puts("");156 return;157 }158 159 int main() {160 int n;161 scanf("%d", &n);162 for(int i = 1; i <= n; i++) {163 scanf("%d", &A[i]);164 }165 root = build(0, n + 1, 0);166 //out(root);167 //puts("");168 for(int i = 1, x, y, z, f; i <= n; i++) {169 scanf("%d%d%d%d", &f, &x, &y, &z);170 if(!f) {171 A[1] = y;172 insert(x - 1, 1);173 }174 else {175 ask(y, y);176 }177 //out(root);178 //puts("");179 }180 181 return 0;182 }
总结：分块就是暴力乱搞......不过很有效，还可能是正解。还能干一些别的数据结构搞不倒的事。