题解 P5070 【[Ynoi2015]即便看不到未来】
诗乃
2019-11-04 22:16:07
离线询问，将询问按照右端点排序，依次加入每个数后统计以该数为右端点的询问区间的答案。
不难发现，设数字$x$上一次出现的位置为$las_x$，则新加入一个$x$对于$las_x$前面的区间没有影响。
由于只需要统计10以下的极长值域连续段，考虑暴力。设当前加入的数字为$x$，则将值域在$[x-11,x+11]$的数字全部提取出来按最后一次出现位置从右往左统计答案。
考虑移动右端点可能增加的方案数，设当前要加入的数字为$x$，可能发生以下几种情况：
1、某值域连续段下面（最低处）加上了$x$。
2、某值域连续段上面（最高处）加上了$x$。
3、某两个值域连续段通过$x$连成一个新的值域连续段。
当发生3时，1和2都不再是极长连续值域段。将1、2情况删除，加入3情况即可。
考虑维护一个序列$b_{l, r}$表示当前右端点为$r$，左端点为$l$的答案。
枚举右端点，按最后一次出现位置从右往左加入左端点统计答案，每次加入一个左端点时按上面三种情况分别统计产生的贡献时，不难发现当$b_{l,r}$被改变时，有一段区间的答案都会被改变。需要一个支持区间加单点查询的数据结构来维护。选用树状数组。
代码：（其实和memset0巨巨写的好像差不多？）
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000050;
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Q {int l, p;}; vector <Q> s[MAXN];
int n, m, a[MAXN], ans[MAXN][30], las[MAXN]; bool vis[MAXN];
struct D {
int p, c;
bool operator < (const D &b) const {return p > b.p;}
};
struct BITS {
int t[MAXN];
void modify(int x, int k) {for(; x; t[x] += k, x -= x&-x);}
int query(int x) {int z = 0; for(; x <= n; z += t[x], x += x&-x); return z;}
} t[30];
int main() {
read(n); read(m); for(int i = 1; i <= n; ++i) read(a[i]);
for(int l, r, i = 1; i <= m; ++i) read(l), read(r), s[r].push_back((Q) {l, i});
for(int i = 1; i <= n; ++i) {
vector <D> q; vector <int> del;
for(int j = max(1, a[i] - 11); j <= a[i] + 11; ++j)
if(las[j] && las[j] > las[a[i]]) q.push_back((D) {las[j], j});
vis[a[i]] = 1; q.push_back((D) {las[a[i]], -1}); q.push_back((D) {i, a[i]});
sort(q.begin(), q.end());
for(int U, L = 0, R = 0, j = 0; j < q.size() - 1; ++j) {
if(~q[j].c) vis[q[j].c] = 1, del.push_back(q[j].c);
for(; vis[a[i]-L-1]; ++L); for(; vis[a[i]+R+1]; ++R);
U = L + R + 1;
if(1 <= L && L <= 10) t[L].modify(q[j].p, -1), t[L].modify(q[j+1].p, 1);
if(1 <= R && R <= 10) t[R].modify(q[j].p, -1), t[R].modify(q[j+1].p, 1);
if(1 <= U && U <= 10) t[U].modify(q[j].p, 1), t[U].modify(q[j+1].p, -1);
} vis[a[i]] = 0;
for(int j = 0; j < del.size(); ++j) vis[del[j]] = 0;
for(int j = 0; j < s[i].size(); ++j)
for(int k = 1; k <= 10; ++k)
ans[s[i][j].p][k] = t[k].query(s[i][j].l);
las[a[i]] = i;
}
for(int i = 1; i <= m; ++i) {
for(int j = 1; j <= 10; ++j)
putchar(ans[i][j] % 10 + 48);
putchar('\n');
}
}
```