题目描述
加里敦大学有个帝国图书馆，小豆是图书馆阅览室的一个书籍管理员。他的任务是把书排成有序的，所以无序的书让他产生厌烦，两本乱序的书会让小豆产生这两本书页数的和的厌烦度。现在有n本被打乱顺序的书，在接下来m天中每天都会因为读者的阅览导致书籍顺序改变位置。因为小豆被要求在接下来的m天中至少要整理一次图书。小豆想知道，如果他前i天不去整理，第i天他的厌烦度是多少，这样他好选择厌烦度最小的那天去整理。
## 输入输出格式
输入格式：
第一行会有两个数，n，m分别表示有n本书，m天
接下来n行，每行两个数，ai和vi，分别表示第i本书本来应该放在ai的位置，这本书有vi页，保证不会有放置同一个位置的书
接下来m行，每行两个数，xj和yj，表示在第j天的第xj本书会和第yj本书会因为读者阅读交换位置
输出格式：
一共m行，每行一个数，第i行表示前i天不去整理，第i天小豆的厌烦度，因为这个数可能很大，所以将结果模10^9 +7后输出.
输入输出样例
输入样例#1： 复制
5 5
1 1
2 2
3 3
4 4
5 5
1 5
1 5
2 4
5 3
1 3
输出样例#1： 复制
42
0
18
28
48
说明
对于20%的数据，1 ≤ ai; xj; yj ≤ n ≤ 5000, m ≤ 5000, vi ≤ 10^5
对于100%的数据，1 ≤ ai; xj; yj ≤ n ≤ 50000, m ≤ 50000, vi ≤ 10^5
Solution
看一波数据范围,50000,5s。猜一波时间复杂度，\(nlogn^2\)?\(nlogn^3\)?\(nlogn^2\sqrt n\)?
想了一波树套树，发现可以做。这里我用的是树状数组套主席树。
题目大意就是给你一些数对，每个数有一个权值，也有一个厌烦度。
当一对数为逆序对，然后算总厌烦度。可以发现这题和[CQOI2011]动态逆序对很像，只不过这里有一个厌烦度，动态逆序对那道题相当于权值为1，所以这道题是那道题的升级版。
可以理解，题目中所说的本来位置，就是指判断当前这对数是否是逆序对中的标准，也就是逆序对中数的权值。
我们每次只需统计前面比他小的数字厌烦度之和是多少，并且存下有多少个比他小，设当前数字的位置为\(x\),它的本来位置为\(a[x]\)(也就是判断逆序对的权值)，每个数字的厌烦度为\(w[i]\),所以当前这个数与其他数产生的厌烦度为
\]
但想到若两个交换的数字为逆序对，那么需要特殊判断。
还要注意细节，本题要开\(long long\),而且要注意取模和空间问题。
主席树的节点都开\(long long\)就会爆空间。
代码如下:
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct TREE
{
int ln,rn,shu;
ll zhi;
}t[15001000];
int root[210000];
ll tot,a[101000],hash[101001],n,m,id[101000],w[109101];
ll qll[20101],qrr[20100],q1,q2,ge,ff=0;
ll lowbit(ll x) {return ((x)&(-x));}
void gai(int &node,int l,int r,ll hs,ll v,ll kk)
{
if(!node) node=++tot;
t[node].zhi+=v;
t[node].shu+=kk;
if(l==r) return;
ll mid=(l+r)/2;
if(hs<=mid) gai(t[node].ln,l,mid,hs,v,kk);
else gai(t[node].rn,mid+1,r,hs,v,kk);
}
void add(ll p,ll v,ll kk){for(ll i=p;i<=n;i+=lowbit(i)) gai(root[i],1,n,hash[p],v,kk);}
ll SUM()
{
ll ans1=0,ans2=0;ff=0;
for(ll i=1;i<=q1;i++) ans1+=t[t[qrr[i]].ln].zhi,ff+=t[t[qrr[i]].ln].shu;
for(ll i=1;i<=q2;i++) ans2+=t[t[qll[i]].ln].zhi,ff-=t[t[qll[i]].ln].shu;
return ans1-ans2;
}
ll rk(ll qr,ll ql,ll l,ll r,ll k)
{
q1=0;q2=0;ll ans=0;ge=0;
for(ll i=qr;i>=1;i-=lowbit(i)) qrr[++q1]=root[i];
for(ll i=ql;i>=1;i-=lowbit(i)) qll[++q2]=root[i];
while(l<r)
{
ll mid=(l+r)/2;
if(k<=a[mid])
{
for(ll i=1;i<=q1;i++) qrr[i]=t[qrr[i]].ln;
for(ll i=1;i<=q2;i++) qll[i]=t[qll[i]].ln;
r=mid;
}
else
{
ll lsiz=SUM();
for(ll i=1;i<=q1;i++) qrr[i]=t[qrr[i]].rn;
for(ll i=1;i<=q2;i++) qll[i]=t[qll[i]].rn;
l=mid+1;ans+=lsiz;ge+=ff;
}
}
return ans;
}
ll SUM1()
{
ll ans1=0,ans2=0;ff=0;
for(ll i=1;i<=q1;i++) ans1+=t[t[qrr[i]].rn].zhi,ff+=t[t[qrr[i]].rn].shu;
for(ll i=1;i<=q2;i++) ans2+=t[t[qll[i]].rn].zhi,ff-=t[t[qll[i]].rn].shu;
return ans1-ans2;
}
ll rkk(ll qr,ll ql,ll l,ll r,ll k)
{
q1=0;q2=0;ll ans=0;ge=0;
for(ll i=qr;i>=1;i-=lowbit(i)) qrr[++q1]=root[i];
for(ll i=ql;i>=1;i-=lowbit(i)) qll[++q2]=root[i];
while(l<r)
{
ll mid=(l+r)/2;
if(k<=a[mid])
{
ll rsiz=SUM1();
for(ll i=1;i<=q1;i++) qrr[i]=t[qrr[i]].ln;
for(ll i=1;i<=q2;i++) qll[i]=t[qll[i]].ln;
r=mid;ans+=rsiz;ge+=ff;
}
else
{
for(ll i=1;i<=q1;i++) qrr[i]=t[qrr[i]].rn;
for(ll i=1;i<=q2;i++) qll[i]=t[qll[i]].rn;
l=mid+1;
}
}
return ans;
}
int main()
{
ll x,y;
long long ans=0;
cin>>n>>m;
for(ll i=1;i<=n;i++)
scanf("%lld%lld",&a[i],&w[i]),hash[i]=a[i],id[a[i]]=i;
sort(a+1,a+1+n);
for(ll i=1;i<=n;i++)
add(i,w[i],1);
for(ll i=1;i<=n;i++)
{
ans+=rkk(i-1,0,1,n,hash[i]);
ans+=rk(n,i,1,n,hash[i]);
}
for(ll i=1;i<=m;i++)
{
ll x1,y1;
scanf("%lld%lld",&x,&y);
x1=x;y1=y;
ans-=(rkk(x1-1,0,1,n,hash[x1])+ge*w[x1]);
ans-=(rk(n,x1,1,n,hash[x1])+ge*w[x1]);
ans-=(rkk(y1-1,0,1,n,hash[y1])+ge*w[y1]);
ans-=(rk(n,y1,1,n,hash[y1])+ge*w[y1]);
if((x1<y1&&hash[x1]>hash[y1])||(x1>y1&&hash[x1]<hash[y1]))
ans+=w[x1]+w[y1];
add(x1,-w[x1],-1);add(y1,-w[y1],-1);
swap(hash[x1],hash[y1]);swap(w[x1],w[y1]);
add(x1,w[x1],1);add(y1,w[y1],1);
x1=x;y1=y;
ans+=(rkk(x1-1,0,1,n,hash[x1])+ge*w[x1]);
ans+=(rk(n,x1,1,n,hash[x1])+ge*w[x1]);
ans+=(rkk(y1-1,0,1,n,hash[y1])+ge*w[y1]);
ans+=(rk(n,y1,1,n,hash[y1])+ge*w[y1]);
if((x1<y1&&hash[x1]>hash[y1])||(x1>y1&&hash[x1]<hash[y1]))
ans-=(w[x1]+w[y1]);
printf("%lld\n",ans%mod);
}
}
博主蒟蒻，可以随意转载，但必须附上原文链接k-z-j。