Codeforces 633H Fibonacci-ish II
問題概要: 区間をソートした後重複を取り除き、さらにそのi項目にフィボナッチ数列のi項目をかけたものの和を求めるクエリを30000個くらい処理せよ。
解法:
最初に思いついたのが、区間を平方分割して、クエリを終点でソートし、sqrt(N)個のsegtreeを始点をずらして作って一番近いところを少し動かしてクエリにこたえるという方法で、実装したらTLEしたので解説を見た。Moというものがあるらしい。(オーダーは同じ)
Moをやってもなおバケットサイズを気を付けないと通らないしpretest形式で出すものではないと思う。フィボナッチをのせるsegtreeは大昔に一度書いたけど完全に忘却していた。遅延更新が異常な量あるしそりゃ定数倍も重いわという感じ。
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; #define SIZE 32768 int mod; int fib[100000]; int rfib[100000]; class BIT { public: int bit[SIZE + 1]; void add(int a, int b) { a++; for (;;) { bit[a] += b; a += a&-a; if (a > SIZE)return; } } int get(int a) { a++; int ret = 0; for (;;) { ret += bit[a]; a -= a&-a; if (a == 0)return ret; } } }; class segtree { public: int seg[SIZE * 2]; int pl[SIZE * 2]; int flag[SIZE * 2]; void update(int beg, int end, int node, int lb, int ub, int n) { if (ub < beg || end < lb)return; if (beg <= lb&&ub <= end) { if (n == 1) { int t = pl[node]; pl[node] = seg[node]; seg[node] = (seg[node] + t) % mod; flag[node]++; } else { int t = seg[node]; seg[node] = pl[node]; pl[node] = (t + mod - pl[node]) % mod; flag[node]--; } return; } if (flag[node]) { if (flag[node] > 0) { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2 + 1] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; } else { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2 + 1] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; } flag[node * 2] += flag[node]; flag[node * 2 + 1] += flag[node]; flag[node] = 0; } update(beg, end, node * 2, lb, (lb + ub) / 2, n); update(beg, end, node * 2 + 1, (lb + ub) / 2 + 1, ub, n); seg[node] = (seg[node * 2] + seg[node * 2 + 1])%mod; pl[node] = (pl[node * 2] + pl[node * 2 + 1])%mod; } void add(int p, int node, int lb, int ub, int t1, int t2) { if (ub < p || p < lb)return; if (lb == ub) { seg[node] += t1; pl[node] += t2; seg[node] %= mod; pl[node] %= mod; // printf("add %d %d %d\n", lb, t1, t2); return; } if (flag[node]) { if (flag[node] > 0) { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2 + 1] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; } else { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2 + 1] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; } flag[node * 2] += flag[node]; flag[node * 2 + 1] += flag[node]; flag[node] = 0; } add(p, node * 2, lb, (lb + ub) / 2, t1, t2); add(p, node * 2 + 1, (lb + ub) / 2 + 1, ub, t1, t2); seg[node] = (seg[node * 2] + seg[node * 2 + 1]) % mod; pl[node] = (pl[node * 2] + pl[node * 2 + 1]) % mod; //printf("node: %d %d %d\n", node, seg[node], pl[node]); } }; #define B 300 segtree tree; BIT bi; typedef pair<int, int>pii; typedef pair<pii, pii>pi4; int ans[30000]; int cnt[30000]; int main() { int num; scanf("%d%d", &num, &mod); vector<int>vec; vector<int>zat; for (int i = 0; i < num; i++) { int z; scanf("%d", &z); vec.push_back(z); zat.push_back(z); } sort(zat.begin(), zat.end()); int query; scanf("%d", &query); vector<pi4>dat; for (int i = 0; i < query; i++) { int za, zb; scanf("%d%d", &za, &zb); za--; zb--; dat.push_back(make_pair(make_pair(zb / B, za), make_pair(zb, i))); } fib[1] = rfib[1] = 1; for (int i = 2; i < 50000; i++) { fib[i] = (fib[i - 1] + fib[i - 2]) % mod; rfib[i] = (rfib[i - 2] + mod - rfib[i - 1]) % mod; } sort(dat.begin(), dat.end()); int nl = 0, nr = -1; for (int i = 0; i < query; i++) { int beg = dat[i].first.second, end = dat[i].second.first, idx = dat[i].second.second; for (int p=0;;p++) { //printf("%d %d %d\n", nl, nr, tree.seg[1]); if (nl > beg) { nl--; int low = lower_bound(zat.begin(), zat.end(), vec[nl]) - zat.begin(); if (cnt[low] == 0) { int t = bi.get(low); tree.add(low, 1, 0, SIZE - 1, vec[nl] % mod*fib[t + 1] % mod, vec[nl] % mod*fib[t] % mod); tree.update(low + 1, SIZE - 1, 1, 0, SIZE - 1, 1); bi.add(low, 1); } cnt[low]++; } else if (nr < end) { nr++; int low = lower_bound(zat.begin(), zat.end(), vec[nr]) - zat.begin(); if (cnt[low] == 0) { int t = bi.get(low); tree.add(low, 1, 0, SIZE - 1, vec[nr] % mod*fib[t + 1] % mod, vec[nr] % mod*fib[t] % mod); tree.update(low + 1, SIZE - 1, 1, 0, SIZE - 1, 1); bi.add(low, 1); } cnt[low]++; } else if (nl < beg) { int low = lower_bound(zat.begin(), zat.end(), vec[nl]) - zat.begin(); if (cnt[low] == 1) { int t = bi.get(low - 1); tree.add(low, 1, 0, SIZE - 1, (mod - vec[nl] % mod*fib[t + 1] % mod) % mod, (mod - vec[nl] % mod*fib[t] % mod) % mod); tree.update(low + 1, SIZE - 1, 1, 0, SIZE - 1, -1); bi.add(low, -1); } nl++; cnt[low]--; } else if (nr > end) { int low = lower_bound(zat.begin(), zat.end(), vec[nr]) - zat.begin(); if (cnt[low] == 1) { int t = bi.get(low - 1); tree.add(low, 1, 0, SIZE - 1, (mod - vec[nr] % mod*fib[t + 1] % mod) % mod, (mod - vec[nr] % mod*fib[t] % mod) % mod); tree.update(low + 1, SIZE - 1, 1, 0, SIZE - 1, -1); bi.add(low, -1); } nr--; cnt[low]--; } else break; } ans[idx] = tree.seg[1]; } for (int i = 0; i < query; i++)printf("%d\n", ans[i]); }
以下TLE解
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; #define SIZE 32768 int mod; int fib[100000]; int rfib[100000]; class BIT { public: int bit[SIZE + 1]; void add(int a, int b) { a++; for (;;) { bit[a] += b; a += a&-a; if (a > SIZE)return; } } int get(int a) { a++; int ret = 0; for (;;) { ret += bit[a]; a -= a&-a; if (a == 0)return ret; } } }; class segtree { public: int seg[SIZE * 2]; int pl[SIZE * 2]; int flag[SIZE * 2]; void update(int beg, int end, int node, int lb, int ub, int n) { if (ub < beg || end < lb)return; if (beg <= lb&&ub <= end) { if (n == 1) { int t = pl[node]; pl[node] = seg[node]; seg[node] = (seg[node] + t) % mod; flag[node]++; } else { int t = seg[node]; seg[node] = pl[node]; pl[node] = (t + mod - pl[node]) % mod; flag[node]--; } return; } if (flag[node]) { if (flag[node] > 0) { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2 + 1] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; } else { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2 + 1] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; } flag[node * 2] += flag[node]; flag[node * 2 + 1] += flag[node]; flag[node] = 0; } update(beg, end, node * 2, lb, (lb + ub) / 2, n); update(beg, end, node * 2 + 1, (lb + ub) / 2 + 1, ub, n); seg[node] = (seg[node * 2] + seg[node * 2 + 1])%mod; pl[node] = (pl[node * 2] + pl[node * 2 + 1])%mod; } void add(int p, int node, int lb, int ub, int t1, int t2) { if (ub < p || p < lb)return; if (lb == ub) { seg[node] += t1; pl[node] += t2; seg[node] %= mod; pl[node] %= mod; // printf("add %d %d %d\n", lb, t1, t2); return; } if (flag[node]) { if (flag[node] > 0) { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*fib[flag[node] + 1] + b*fib[flag[node]]) % mod; pl[node * 2 + 1] = (a*fib[flag[node]] + b*fib[flag[node] - 1]) % mod; } else { int a = seg[node * 2], b = pl[node * 2]; seg[node * 2] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; a = seg[node * 2 + 1], b = pl[node * 2 + 1]; seg[node * 2 + 1] = (a*rfib[-flag[node] - 1] + b*rfib[-flag[node]]) % mod; pl[node * 2 + 1] = (a*rfib[-flag[node]] + b*rfib[-flag[node] + 1]) % mod; } flag[node * 2] += flag[node]; flag[node * 2 + 1] += flag[node]; flag[node] = 0; } add(p, node * 2, lb, (lb + ub) / 2, t1, t2); add(p, node * 2 + 1, (lb + ub) / 2 + 1, ub, t1, t2); seg[node] = (seg[node * 2] + seg[node * 2 + 1]) % mod; pl[node] = (pl[node * 2] + pl[node * 2 + 1]) % mod; //printf("node: %d %d %d\n", node, seg[node], pl[node]); } }; #define B 200 #define NB 150 segtree tree[NB]; BIT bi[NB]; typedef pair<int, int>pii; vector<pii>dat[30000]; int ans[30000]; int main() { int num; scanf("%d%d", &num, &mod); vector<int>vec; vector<int>zat; for (int i = 0; i < num; i++) { int z; scanf("%d", &z); vec.push_back(z); zat.push_back(z); } sort(zat.begin(), zat.end()); int query; scanf("%d", &query); for (int i = 0; i < query; i++) { int za, zb; scanf("%d%d", &za, &zb); za--; zb--; dat[zb].push_back(make_pair(za, i)); } fib[1] = rfib[1] = 1; for (int i = 2; i < 50000; i++) { fib[i] = (fib[i - 1] + fib[i - 2]) % mod; rfib[i] = (rfib[i - 2] + mod - rfib[i - 1]) % mod; } //for (int i = 0; i < 10; i++)printf(" %d\n", rfib[i]); for (int i = 0; i < num; i++) { //printf("now: %d\n", i); for (int j = 0; j < NB; j++) { if (i >= j*B) { int low = lower_bound(zat.begin(), zat.end(), vec[i]) - zat.begin(); if (bi[j].get(low) == bi[j].get(low - 1)) { int t = bi[j].get(low); tree[j].add(low, 1, 0, SIZE - 1, vec[i] % mod*fib[t + 1] % mod, vec[i] % mod*fib[t] % mod); tree[j].update(low + 1, SIZE - 1, 1, 0, SIZE - 1, 1); //printf(" %d %d %d %d %d\n",j, low, vec[i], vec[i] % mod*fib[t + 1] % mod, vec[i] % mod*fib[t] % mod); bi[j].add(low, 1); } } } /*for (int j = 0; j < 5; j++) { printf("%d ", tree[j].seg[1]); } printf("\n");*/ for (int j = 0; j < dat[i].size(); j++) { int b = (dat[i][j].first + B - 1) / B; if (i <= b * B) { vector<int>v; for (int k = dat[i][j].first; k <= i; k++) { v.push_back(vec[k]); } sort(v.begin(), v.end()); int now = -1, pt = 0; for (int k = 0; k < v.size(); k++) { if (now != v[k]) { now = v[k]; ans[dat[i][j].second] += now%mod*fib[pt + 1]; pt++; ans[dat[i][j].second] %= mod; } } continue; } //printf("query: %d %d %d\n", dat[i][j].first, i, b); vector<pii>zv; for (int k = b*B - 1; k >= dat[i][j].first; k--) { int low = lower_bound(zat.begin(), zat.end(), vec[k]) - zat.begin(); if (bi[b].get(low) == bi[b].get(low - 1)) { int t = bi[b].get(low); tree[b].add(low, 1, 0, SIZE - 1, vec[k] % mod*fib[t + 1] % mod, vec[k] % mod*fib[t] % mod); tree[b].update(low + 1, SIZE - 1, 1, 0, SIZE - 1, 1); //printf("%d %d %d, %d\n", low, vec[k] % mod*fib[t + 1] % mod, vec[k] % mod*fib[t] % mod, low + 1); zv.push_back(make_pair(vec[k], t)); bi[b].add(low, 1); } } ans[dat[i][j].second] = tree[b].seg[1]; for (int k = zv.size() - 1; k >= 0; k--) { int low = lower_bound(zat.begin(), zat.end(), zv[k].first) - zat.begin(); tree[b].update(low + 1, SIZE - 1, 1, 0, SIZE - 1, -1); tree[b].add(low, 1, 0, SIZE - 1, (mod - zv[k].first % mod*fib[zv[k].second + 1] % mod) % mod, (mod - zv[k].first % mod*fib[zv[k].second] % mod) % mod); //printf("%d %d %d, %d\n", low, 0, 0, low + 1); bi[b].add(low, -1); } } /*for (int j = 0; j < 5; j++) { printf("%d ", tree[j].seg[1]); } printf("\n");*/ } for (int i = 0; i < query; i++)printf("%d\n", ans[i]); }