[Ynoi2015] 我回来了

题传

7 个月后再来看这道题，还是感觉太妙了。

由于答案最终输出 /(E /times Len/)，所以本质上是问 /(/forall d /in[L, R]/) 的贡献和，再进一步想，亵渎的要求就是寻找序列

/[x_i=/varepsilon(/exists h_i| h_i/in [(i-1)d+1, id])
/]

从 /(i=1/) 开始的最长连续的 1 段，最长段不好求，转化为求结束的位置，设 /(pos_x/) 为高度 /(x/) 最早出现的位置（不存在则为 /(0/)），则结束的位置 /(end/) 应该满足：

/[/varepsilon(/nexists h_i| h_i/in [(end-1)d+1, end/times d])=/sum_{i=(end-1)d+1}^{end/times d} pos_i=0
/]

现在要搞定的就是这个东西了。

考虑没有增加随从操作怎么做，由于每一个不同的 /(d/) 最多形成的块有 /(n+n/2+n/3+/dots+n/n=n/ln(n)/) 个，我们直接暴力把这 /(n/ln(n)/) 个块的答案整出来（其实也就是对于每个 /(d/)，把对应的 /(x_i/) 搞出）。

考虑记 /(time_{d, i}/) 为块长为 /(d/) 时，第 /(i/) 个块最早什么时候有 1，不难写出：

/[time_{d_,i}=/min_{(i-1)d+1/le j/le id} pos_j
/]

这个显然就可以 ST 表做出来了把，复杂度 /(O(n /log n+n/ln(n))/) 分别是 ST 表预处理的 /(O(n /log n)/)，询问个数 /(n/ln(n)/) 乘上 ST 表询问复杂度 /(O(1)/) 的 /(O(n/ln(n))/)。

显然第 /(i/) 块产生贡献需要满足前 /(i-1/) 块都有值，所以我们还需要对每一个 /(time_{d, i}/) 取前缀 /(/max/)。

现在我们得到了这个 /(time_{d, i}/)，也就相当于知道了这一块的贡献将在什么时候产生，直接丢到这个时刻上面就行了，单点修改、区间查询，显然树状数组更好。

复杂度 /(O(n/ln(n)/log n)=O(n/log^2n)/)。

Code：

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <cctype> 
using namespace std;
inline int read(){
	char ch=getchar();int x=0, f=1;
	while(!isdigit(ch)) f=(ch=='-'?-1:f), ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
	return x*f;
}
const int N=1e5+5;
const int M=1e6+5;
int n, m, lg[N], f[N][20], pos[N];
vector <int> V[M];
pair <int, int> box[M];
int query(int l, int r){//查询最小值 
	int k=lg[r-l+1];
	return min(f[l][k], f[r-(1<<k)+1][k]);
}
int BIT[N];
#define lowbit(x) (x&(-x))
void add(int x){for(; x<=n; x+=lowbit(x)) BIT[x]++;}
int query(int x){
	int ret=0;
	for(; x; x-=lowbit(x)) ret+=BIT[x];
	return ret;
}
#undef lowbit
inline int min(int a, int b){return a=(a<b?a:b);}
int main(){
	n=read(), m=read();
	for(int i=1; i<=n; i++) pos[i]=m+1;
	for(int i=1, opt, x; i<=m; i++){
		opt=read();
		if(opt&1) x=read(), pos[x]=min(pos[x], i), box[i].first=false;
		else box[i].first=read(), box[i].second=read();
	}
	for(int i=2; i<=n; i++) lg[i]=lg[i>>1]+1;
	for(int i=1; i<=n; i++) f[i][0]=pos[i];
	for(int j=1; j<=18; j++)
		for(int i=1; i+(1<<j)-1<=n; i++)
			f[i][j]=min(f[i][j-1], f[i+(1<<j-1)][j-1]);
	for(int d=1; d<=n; d++){
		int Mx=0, tim;add(d);
		for(int l=1, r; l<=n; l=r+1){
			r=min(n, l+d-1);
			tim=query(l, r);Mx=max(Mx, tim);//求出 time(d,j) 并取前缀 max
			V[Mx].push_back(d); 
		}
	}
	for(int i=1; i<=m; i++){
		for(auto j : V[i]) add(j);
		if(box[i].first) printf("%d/n", query(box[i].second)-query(box[i].first-1));
	}
	return 0;
}