【BZOJ4889】不勤劳的图书管理员（树套树）

题面

又是权限题，烦死了

洛谷真好

题解

分开考虑每一次交换产生的贡献。

假设交换\((x,y)\)

检查\(x\)与\(y\)对于区间\([x+1,y-1]\)产生的贡献

再考虑一下\(x,y\)之间的贡献就好啦。

区间的贡献显然是区间内比他小的数的个数乘上当前位置的权值

以及区间内比他小的数的权值和，树套树实现。

具体的再说清楚这题的意思，因为我一开始理解错了。

逆序对的含义是关于\(a_i\)的逆序对

交换是交换第\(i\)个数和第\(j\)个数。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MOD 1000000007

#define MAX 55555

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

int lb(int x){return x&(-x);}

int n,m,V[MAX],ans,p[MAX],a[MAX];

int rt[MAX],tot;

struct Node{int ls,rs,v,s;}t[MAX*200];

void Modify(int &x,int l,int r,int p,int w1,int w2)

{

	if(!x)x=++tot;add(t[x].v,w1);add(t[x].s,w2);

	if(l==r)return;int mid=(l+r)>>1;

	if(p<=mid)Modify(t[x].ls,l,mid,p,w1,w2);

	else Modify(t[x].rs,mid+1,r,p,w1,w2);

}

void Query(int &x,int l,int r,int L,int R,int &s1,int &s2)

{

	if(!x)return;

	if(L<=l&&r<=R){add(s1,t[x].v);add(s2,t[x].s);return;}

	int mid=(l+r)>>1;

	if(L<=mid)Query(t[x].ls,l,mid,L,R,s1,s2);

	if(R>mid)Query(t[x].rs,mid+1,r,L,R,s1,s2);

}

void Modify(int x,int p,int w1,int w2)

{

	for(int i=x;i<=n;i+=lb(i))

		Modify(rt[i],1,n,p,w1,w2);

}

void Query(int l,int r,int L,int R,int &s1,int &s2)

{

	if(L>R)return;int m1=0,m2=0;

	for(int i=r;i;i-=lb(i))Query(rt[i],1,n,L,R,s1,s2);

	for(int i=l-1;i;i-=lb(i))Query(rt[i],1,n,L,R,m1,m2);

	s1=(s1+MOD-m1)%MOD;s2=(s2+MOD-m2)%MOD;

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=n;++i)p[i]=read(),V[i]=read();

	for(int i=1;i<=n;++i)

	{

		int s1=0,s2=0;

		Modify(i,p[i],V[i],1);

		Query(1,i-1,p[i]+1,n,s1,s2);

		add(ans,s1);add(ans,1ll*s2*V[i]%MOD);

	}

	while(m--)

	{

		int x=read(),y=read(),s1,s2,m1,m2;

		if(x>y)swap(x,y);int a=p[x],b=p[y];

		s1=s2=m1=m2=0;

		Query(x+1,y-1,a+1,n,s1,s2);Query(x+1,y-1,1,a-1,m1,m2);

		add(s1,MOD-m1);add(s2,MOD-m2);

		add(ans,s1);add(ans,1ll*s2*V[x]%MOD);

		s1=s2=m1=m2=0;

		Query(x+1,y-1,1,b-1,s1,s2);Query(x+1,y-1,b+1,n,m1,m2);

		add(s1,MOD-m1);add(s2,MOD-m2);

		add(ans,s1);add(ans,1ll*s2*V[y]%MOD);

		if(a<b)add(ans,V[x]+V[y]);

		if(a>b)add(ans,MOD-(V[x]+V[y]));

		Modify(x,a,MOD-V[x],MOD-1);Modify(y,a,V[x],1);

		Modify(y,b,MOD-V[y],MOD-1);Modify(x,b,V[y],1);

		swap(p[x],p[y]);swap(V[x],V[y]);printf("%d\n",ans);

	}

}