lyzlyz?lyzlyz!

问：你这个乡村学校的小学生，为什么要学劼劼劼呢？

答：因为窝一下做了太多的树状数组，懒得一篇一篇写了。

问：既然线段树可以代替树状数组，那么为什么要树状数组呢？

答：树状数组好写啊Orz。

问：那我可以不看冗长的介绍过程吗？

答：如果机房的门要关了或者你急着要泡妹子，请跳至最后一目。

【简介】

首先普通的一维树状数组就不说了，如果你不知道，戳这。

那么窝萌阔以看到：普通的树状数组支持单点修改、片段和。

显然树状数组是解决逆序对问题的最好方法。

某大神表示阔以用树状数组来维护区间最值，不明觉厉~

inline void init()  
{  
    CLR(arr,0);  
    for(int i=1;i<=N;++i)  
        for(int j=i;j<=N&&arr[j]<num[i];j+=lowbit(j))  
            arr[j]=num[i];  
}  
inline int query(int L,int R)  
{  
    int res=0;  
    for(--L;L<R;){  
        if(R-lowbit(R)>=L){res=max(res,arr[R]);R-=lowbit(R);}  
        else{res=max(res,num[R]);--R;}  
    }  
    return res;  
}  
inline void update(int x,int val)  
{  
    int ori=num[x];  
    num[x]=val;  
    if(val>=ori)  
        for(int i=x;i<=N&&arr[i]<val;i+=lowbit(i))  
            arr[i]=val;  
    else{  
        for(int i=x;i<=N&&arr[i]==ori;i+=lowbit(i))  
        {  
            arr[i]=val;  
            for(int j=lowbit(i)>>1;j;j>>=1)  
                arr[i]=max(arr[i],arr[i-j]);  
        }  
    }  
}  

那么树状数组可不可以支持区间修改呢？

 

让窝萌先来解决一个子问题：维护一个序列，支持区间修改、单点求值。

那么差分，令d[i]=a[i]-a[i-1]，d[1]=a[1]，那么显然[tex]a[i] = \sum\limits_{j = 1}^n {d[j]}[/tex]

修改区间[l,r]，则可以通过前缀和得到：d[l]+=k,d[r+1]-=k。

 

那么要求区间和怎么办呢？

通过简单的推导可以得到：

[tex]\sum\limits_{i = 1}^x {a[i]}  = \sum\limits_{i = 1}^x {d[i]*(x - i + 1) = (x + 1)*\sum\limits_{i = 1}^x {d[i]}  - \sum\limits_{i = 1}^x {d[i]*i} }[/tex]

那么再开一个树状数组来维护d[i]*i就阔以辣！

 

接着看二维树状数组。

显然根据树状数组的定义再加一维就阔以了。

即令tree[i][j]为矩阵[i-lowbit(i)+1,j-lowbit(j)+1]~[i,j]的片段和。

对于二维树状数组的区间修改和求和，可以通过二维前缀和的性质推出。

这里的d[i]有另一个定义，表示i~n这一段的都加上d[i]。

那么扩展到二维，d[i][j]表示矩阵[i,j]~[n,m]的都加上d[i][j]。

修改矩阵[x1,y1]~[x2,y2]，那么d[x1][y1]+=k,d[x1][y2+1]-=k,d[x2+1][y1]-=k,d[x2+1][y2+1]+=k。

求[1,1]~[x,y]，就是p-q。

[tex]p = (x + 1)(y + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]} }  + \sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]*i*j} }[/tex]

[tex]q = (x + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]*j + (y + 1)\sum\limits_{i = 1}^x {\sum\limits_{j = 1}^y {a[i][j]} } } } *i[/tex]

[tex]

显然我讲的很不详细，所以戳这

（悄悄地告诉你其实窝前面也是抄的论文）

【例题】

BZOJ2789

首先看到一个贪心性质，即第一个串中第k次出现的某个字母对应的一定是第二个中第k次出现的。

那么求个逆序对就阔以了。

BZOJ2743

先求出每个元素下一个与它相同的是第几个。

显然如果[l,r]中有两个同样的元素，该元素的编号为i>=l，则next[i]<=r就阔以了。

那么对询问进行离线操作，其余的还是程序说得更清楚，所以开始看程序吧。

BZOJ1452

对于每种颜色开个二维树状数组就水过了。。。

BZOJ3132

论文题，看完了绝逼会做。

BZOJ3038

显然发现了一个神奇的性质：一个数只要开根了7次后就会变成1，然后就不变了。

那么就用并查集维护变成1的区间不用改了，然后用树状数组维护整个序列。

BZOJ1106

如果两个相同的数间有x个未消掉的数，那么就需要交换x次。

那么只要知道区间内只出现过一次的数的个数就阔以啦！

【Codes】

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000010;
int n,i;
long long ans;
char a[M],b[M];
int c[M],tree[M],now[30];
int q[27][M];
int query(int x){
	int ans=0;
	for (int i=x;i>0;i-=i&-i)ans+=tree[i];
	return ans;
}
void update(int x){
	for (int i=x;i<=n;i+=i&-i)tree[i]++;
}
int main(){
	scanf("%d",&n);
	scanf("%s",a+1);
	scanf("%s",b+1);
	for (i=1;i<=n;i++)q[a[i]-'A'][++q[a[i]-'A'][0]]=i;
	for (i=1;i<=n;i++)c[i]=q[b[i]-'A'][++now[b[i]-'A']];
	for (i=n;i>=1;i--){
		ans+=query(c[i]);
		update(c[i]);
	}
	printf("%lld\n",ans);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1000010;
int n,m,p,i,l;
int a[M],now[M],next[M],ans[M],tree[M];
struct shit{int l,r,id;}q[M];
int cmp(shit a,shit b){return a.l<b.l;}
int query(int x){
	int ans=0;
	for (int i=x;i>0;i-=i&-i)ans+=tree[i];
	return ans;
}
void update(int x,int p){
	for (int i=x;i<=n;i+=i&-i)tree[i]+=p;
}
int main(){
	scanf("%d%d%d",&n,&p,&m);
	for (i=1;i<=n;i++)scanf("%d",&a[i]);
	for (i=n;i>0;i--)next[i]=now[a[i]],now[a[i]]=i;
	for (i=1;i<=p;i++)if (next[now[i]])update(next[now[i]],1);
	for (i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	l=1;
	for (i=1;i<=m;i++){
		while (l<q[i].l){
			if (next[l])update(next[l],-1);
			if (next[next[l]])update(next[next[l]],1);
			l++;
		}
		ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
	}
	for (i=1;i<=m;i++)printf("%d\n",ans[i]);
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,i,j,opt,q,x,y,ch,x1,x2,y1,y2;
int a[310][310];
int tree[110][310][310];
void update(int opt,int x,int y,int p){
	for (int i=x;i<=n;i+=i&-i)
		for (int j=y;j<=m;j+=j&-j)
			tree[opt][i][j]+=p;
}
int query(int opt,int x,int y){
	int ans=0;
	for (int i=x;i;i-=i&-i)
		for (int j=y;j;j-=j&-j)
			ans+=tree[opt][i][j];
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++){
			scanf("%d",&a[i][j]);
			update(a[i][j],i,j,1);
		}
	scanf("%d",&q);
	while (q--){
		scanf("%d",&opt);
		if (opt==1){
			scanf("%d%d%d",&x,&y,&ch);
			update(a[x][y],x,y,-1);
			a[x][y]=ch;
			update(a[x][y],x,y,1);
		}else{
			scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&ch);
			printf("%d\n",query(ch,x2,y2)-query(ch,x1-1,y2)-query(ch,x2,y1-1)+query(ch,x1-1,y1-1));
		}
	}
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[10];
int n,m,x1,x2,y1,y2,ch;
int tree[2100][2100][4];
void update(int x,int y,int p){
	for (int i=x;i<=n;i+=i&-i)
		for (int j=y;j<=m;j+=j&-j){
			tree[i][j][0]+=p;
			tree[i][j][1]+=p*x;
			tree[i][j][2]+=p*y;
			tree[i][j][3]+=p*x*y;
		}
}
int query(int x,int y){
	int ans=0;
	for (int i=x;i;i-=i&-i)
		for (int j=y;j;j-=j&-j)
			ans=ans+tree[i][j][0]*(x+1)*(y+1)-tree[i][j][1]*(y+1)-tree[i][j][2]*(x+1)+tree[i][j][3];
	return ans;
}
int main(){
	scanf("%s",s);
	scanf("%d%d",&n,&m);
	while (scanf("%s",s)!=EOF){
		if (s[0]=='L'){
			scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&ch);
			update(x1,y1,ch);
			update(x2+1,y1,-ch);
			update(x1,y2+1,-ch);
			update(x2+1,y2+1,ch);
		}else{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			printf("%d\n",query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1));
		}
	}
}

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
typedef long long ll;
using namespace std;
int n,m,i,opt,x,y;
int f[100010];
ll a[100010],tree[100010];
int search(int x){
	if (!f[x])f[x]=x;
	if (f[x]!=x)f[x]=search(f[x]);
	return f[x];
}
ll query(int x){
	ll ans=0;
	for (int i=x;i;i-=i&-i)ans+=tree[i];
	return ans;
}
void update(int x,ll y){
	for (int i=x;i<=n;i+=i&-i)tree[i]+=y;
}
void solve(int x,int y){
	for (int i=search(x);i<=y;i=search(i+1)){
		ll tmp=(ll)sqrt(a[i]);
		update(i,tmp-a[i]);
		a[i]=tmp;
		if (a[i]<=1)f[i]=search(i+1);
	}
}
int main(){
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if (a[i]<=1)f[i]=i+1;
		update(i,a[i]);
	}
	scanf("%d",&m);
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&opt,&x,&y);
		if (x>y)swap(x,y);
		if (!opt)solve(x,y);else printf("%lld\n",query(y)-query(x-1));
	}
}

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,ans;
int a[100010],tree[100010],pre[100010];
void update(int x,int y){
	for (int i=x;i<=2*n;i+=i&-i)tree[i]+=y;
}
int query(int x){
	int ans=0;
	for (int i=x;i;i-=i&-i)ans+=tree[i];
	return ans;
}
int main(){
	scanf("%d",&n);
	for (i=1;i<=2*n;i++)scanf("%d",&a[i]);
	for (i=1;i<=2*n;i++){
		if (!pre[a[i]])pre[a[i]]=i,update(i,1);
			else{
				ans+=query(i)-query(pre[a[i]]);
				update(pre[a[i]],-1);
			}
	}
	printf("%d\n",ans);
}