首页 > 代码库 > 记一个问题的AC
记一个问题的AC
今天突然做一道LCT的染色问题的时候突然想到一个两个月前一道没有AC的题目。
链接
大意是，给一个长度为10^4的序列，最多有255个不同的数字,有最多10^5次方个询问,对于每个询问 l,r 输出[l,r]中不同数字的数目。
记得最初的想法是 用f[i][j],存下数字i的第j次出现位置的下标 ，对每次询问，二分查找，判断每个数字i是否存在在[l,r]内的下标。
时间复杂度是最多是 O（(10^5)*255*log(10^4)） ，结果比赛的时候超时了，加了读入优化还是不行。
由于比赛的OJ运行偏慢，1s的时限 比赛结束，只有3个人AC，最快的400ms，有一个刚刚好1000ms。
于是我发了个帖子，询问答案，果然得到了更好的思路：
1.
离散化,C[i][j]::A[1]..A[i]中值为j的数的个数
则数k在[L..R]中出现 <=> C[i][R]-C[i][L-1]>0.
一次询问时间(255)，时间复杂度是O（10^5*255）
已经优化了一点点
代码：
#include <cstdio>#include <cstdlib>#include <time.h>#include <iostream>using namespace std;const int INF = 100009;int f[INF][300],pos[INF];int g[INF];int n, m, tol;inline void rd (int &xx) { char ch = getchar(); while (ch < ‘0‘ || ch > ‘9‘) ch = getchar(); for (xx = 0; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar() ) xx = xx * 10 + (ch - ‘0‘);}char o[35];inline void putnum (int x) { if (x == 0) {putchar (‘0‘); return;} int i; for (i = 0; x != 0; i++, x /= 10) o[i] = x % 10 + ‘0‘ ; for (i--; i >= 0; i--) putchar (o[i]); putchar (10);}int main() { rd (n); rd (m); for (int i = 1; i <= n; i++) { rd (g[i]); if (!pos[g[i]]) pos[g[i]] = ++tol; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= tol; j++) f[i][j] = f[i - 1][j] + (pos[g[i]] == j); } for (int i = 1, l, r; i <= m; i++) { int ans = 0; rd (l), rd (r); for (int j = 1; j <= tol; j++) if (f[r][j] - f[l - 1][j]) ans++; putnum (ans); } return 0;}
可是在加上了读入和输出优化和依旧超时！
2.
把所有询问存下来，并按照l由小到大的顺序依次回答。当左端点为t时，考虑一个数组b[],若b[i]=1则表示a[i]在a[t]到a[i-1]都没出现过，否则b[i]=0。
那么任意一个左端点l=t，右端点r的询问都可以查询b[1]到b[r]的和得到答案。这个求区间和的操作可以用树状数组或线段树来解决。
当回答完l=t的询问，要回答l=t+1的询问时，涉及到b[]数组的修改。发现只需要把b[t]由1变0，把b[right[t]]由0变1，其中a[t]右边第一个和它相等的数是a[right[t]]，可以预处理出来。这两个修改对于树状数组来说太容易了，然后本题就做完了。
补一句，如果题目要求强制在线，就把树状数组换成可持久化线段树，就搞定了。
时间复杂度可以优化至 O（NlogN+Q）
思路真是太棒了！看完这个我感觉这就是我想要的。
于是再经过无数TLE，优化，TLE，再优化终于AC了，并且只用了234ms！
#include <cstdio>#include <cstdlib>#include <time.h>#include <iostream>using namespace std;const int INF = 100009;int b[INF], ans[INF], qhead[INF], qr[INF], skip[INF];int g[INF], ne[INF], last[INF];int n, m, tol;inline void rd (int &xx) { char ch = getchar(); while (ch < ‘0‘ || ch > ‘9‘) ch = getchar(); for (xx = 0; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar() ) xx = xx * 10 + (ch - ‘0‘);}char o[35];inline void putnum (int x) { if (x == 0) {putchar (‘0‘); return;} int i; for (i = 0; x != 0; i++, x /= 10) o[i] = x % 10 + ‘0‘ ; for (i--; i >= 0; i--) putchar (o[i]); putchar (10);}int main() { rd (n); rd (m); for (int i = 1; i <= n; i++) rd (g[i]); for (int i = 1, x; i <= m; i++) { rd (x), rd (qr[i]); skip[i] = qhead[x]; qhead[x] = i; } for (int i = 1; i <= n; i++) { int t = g[i]; if (last[t] == 0) for (int x = i; x <= n; x += x & -x) ++b[x]; ne[last[t]] = i, last[t] = i; } for (int i = 1; i <= n; i++) { if (qhead[i]) for (int t = qhead[i]; t; t = skip[t]) for (int x = qr[t]; x > 0; x -= x & -x) ans[t] += b[x]; for (int x = i; x <= n; x += x & -x) --b[x]; if (ne[i] != 0) for (int x = ne[i]; x <= n; x += x & -x) ++b[x]; } for (int i = 1; i <= m; i++) putnum (ans[i]);}
感谢回答我问题的 nodgd 和 Hoblovski
记一个问题的AC