HDE6315 Naive Operations

http://acm.hdu.edu.cn/showproblem.php?pid=6315

线段树维护，只要某个区间里有一个数能加出一个新的 (b_i) 来就递归下去，并更新答案
当然如果没有任何一个数能加出 (b_i) 就停止递归

由于每次只会加一，所以一共最多加 (m)，而 (b) 又是个排列，所以一共加出的新的 (b_i) 个数是 (sum_{i=1}^n frac{m}{i}=O(mln n))
由此即使暴力递归也一共不会修改很多次，加上线段树的复杂度就是 (O(mln nlog n))

这样在线段树上均摊复杂度的题还挺奇妙的，大概就是某些操作不会进行太多次可以暴力做，而同时又可以判断出哪些区间不用递归进去进行操作
大概遇到过这么几个：
http://acm.hdu.edu.cn/showproblem.php?pid=6315
https://www.luogu.com.cn/problem/P3747
https://www.luogu.com.cn/problem/P4145
https://uoj.ac/problem/228

HDE6315 的代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<iomanip>
#include<cstring>
#define reg register
#define EN puts("")
inline int read(){
	register int x=0;register int y=1;
	register char c=std::getchar();
	while(c<'0'||c>'9'){if(c=='-') y=0;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=getchar();}
	return y?x:-x;
}
#define N 100006
struct Node{
	Node *ls,*rs;
	int sum,last,tag;
}dizhi[N*2],*root=&dizhi[0];
int tot;
int b[N];
void build(Node *tree,int l,int r){
	if(l==r) return tree->last=b[l],void();
	tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
	int mid=(l+r)>>1;
	build(tree->ls,l,mid);build(tree->rs,mid+1,r);
}
inline void pushup(Node *tree){
	tree->sum=tree->ls->sum+tree->rs->sum;
	tree->last=std::min(tree->ls->last,tree->rs->last);
}
inline void pushdown(Node *tree,int TTT,int ql,int qr,int l,int r){
	if(!tree->tag) return;
	reg int tag=tree->tag;tree->tag=0;
	tree->ls->last-=tag;tree->rs->last-=tag;
	tree->ls->tag+=tag;tree->rs->tag+=tag;
}
int ask(Node *tree,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return tree->sum;
	pushdown(tree,1,ql,qr,l,r);
	int mid=(l+r)>>1;
	int ret=0;
	if(ql<=mid) ret+=ask(tree->ls,l,mid,ql,qr);
	if(qr>mid) ret+=ask(tree->rs,mid+1,r,ql,qr);
	return ret;
}
void change(Node *tree,int l,int r,int ql,int qr,int added){
	if(ql<=l&&r<=qr){
		if(!added) tree->last--,tree->tag++;
		if(tree->last>0) return;//不会产生新的贡献
		if(l==r){
			if(!tree->last) tree->sum++,tree->last=b[l];
			return;
		}
		added=1;
	}
	pushdown(tree,2,ql,qr,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) change(tree->ls,l,mid,ql,qr,added);
	if(qr>mid) change(tree->rs,mid+1,r,ql,qr,added);
	pushup(tree);
}
int n,m;
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		for(reg int i=1;i<=n;i++) b[i]=read();
		for(reg int i=0;i<N*2;i++)
			dizhi[i].ls=dizhi[i].rs=NULL,dizhi[i].sum=dizhi[i].last=dizhi[i].tag=0;
		tot=0;
		build(root,1,n);
		while(m--){
			char c=getchar();
			while(c!='a'&&c!='q') c=getchar();
			int a=read();
			if(c=='a') change(root,1,n,a,read(),0);
			else printf("%d
",ask(root,1,n,a,read()));
		}
	}
	return 0;
}