【bzoj4889】: [Tjoi2017]不勤劳的图书管理员
题目大意：给定一个序列(n<=50000)，每个数有一个编码ai(ai<=50000)和权值vi(vi<=100000)，每次交换两个数的位置，交换m次(m<=50000)
求每次交换后的序列的杂乱度对1e9+7取模(对于每一对是逆序对的编码会产生两者权值和的杂乱度)。
感觉正解是什么奇怪的树套树？蒟蒻只会分块水题。。
先用BIT求一遍初始状态的杂乱度。。(不要问我为什么一开始是BIT。。因为打暴力正好用到就懒得改了。。感觉直接分块也行)
然后开始分块。。分块完对每个块内排序，然后求出排序完之后的权值前缀和。
考虑每次交换操作，若原有序列是 A B C D E，交换B D
那么其实改变的杂乱度只跟B->D的序列有关，跟A E无关
仔细讨论一下就是
当aB<aD
改变的杂乱度会是
C段里所有编号比aB大的权值和 + C段里所有编号比aB大的个数*vB - C段里所有编号比aB小的权值和 - C段里所有编号比aB小的个数*vB
C段里所有编号比aD小的权值和 + C段里所有编号比aD小的个数*vD - C段里所有编号比aD大的权值和 - C段里所有编号比aD大的个数*vD
当aB>aD
贡献符号相反。
如果B!=D 还会加上 vB+vD的贡献
按照这种讨论在分块里各种暴力瞎搞二分就好了。。
然后最后再把BD所在的块暴力重建就做完了。。
/* http://www.cnblogs.com/karl07/ */
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; #define ll long long
#define lowbit(x) (x&-x)
const int N=1e5+;
const int P=1e9+;
const int MX=1e5;
int n,m,cnt;
int pos[N],st[N];
ll bit[N],bb[N];
ll lst=;
struct data{
int x,y;
}a[N],b[N]; bool oper(data a,data b){
return a.x<b.x;
} void modify(int i){
for (int j=st[i];j<st[i+];j++){
b[j].x=a[j].x;
b[j].y=a[j].y;
}
sort(b+st[i],b+st[i+],oper);
for (int j=st[i]+;j<st[i+];j++){
b[j].y=(b[j].y+b[j-].y)%P;
}
} int find(int l,int r,int x){
int mid=(l+r)/,ans=l-;
while (l<=r){
mid=(l+r)/;
if (b[mid].x<x){
ans=mid;
l=mid+;
}else{
r=mid-;
}
}
return ans;
} ll query(int x,int mn,int mx,int ny,int xy){
int p1=find(st[x],st[x+]-,mx),p2=find(st[x],st[x+]-,mn);
ll ans=;
ans+=(b[p1].y)*(p1>=st[x])+(p1-st[x]+)*xy%P;
ans+=b[st[x+]-].y-b[p2].y*(p2>=st[x])+ny*(st[x+]--p2)%P;
swap(p1,p2);
ans-=(b[p1].y)*(p1>=st[x])+(p1-st[x]+)*ny%P;
ans-=b[st[x+]-].y-b[p2].y*(p2>=st[x])+xy*(st[x+]--p2)%P;
return ans%P;
} void build(){
int sz=sqrt(n)/;
for (int i=;i<=n;i++){
if (sz== || i%sz==){
st[++cnt]=i;
}
pos[i]=cnt;
}
st[cnt+]=n+;
for (int i=;i<=cnt;i++){
modify(i);
}
} void Modify(int x,int y){
while (x<=MX){
bit[x]+=y;
bb[x]++;
bit[x]%=P;
x+=lowbit(x);
}
} ll Query(int x,int y){
ll ans=,a2=;
while (x){
ans+=bit[x];
a2+=bb[x];
ans%=P;
x-=lowbit(x);
}
ans+=a2*y%P;
return ans%P;
} int main(){
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
}
for (int j=;j<=n;j++){
lst+=Query(MX,a[j].y)-Query(a[j].x,a[j].y);
lst%=P;
Modify(a[j].x,a[j].y);
}
build();
for (int i=;i<=m;i++){
int x,y,x1,y1,px,py,mn,mx,ny,xy;
ll ans=;
scanf("%d%d",&x1,&y1);
x=min(x1,y1);
y=max(x1,y1);
px=pos[x],py=pos[y];
if (a[x].x<a[y].x) mn=a[x].x,ny=a[x].y,mx=a[y].x,xy=a[y].y;
else mx=a[x].x,xy=a[x].y,mn=a[y].x,ny=a[y].y;
if (px!=py){
for (int i=x+;i<st[px+];i++){
ans+= (a[i].x>mn)*(a[i].y+ny);
ans+= (a[i].x<mx)*(a[i].y+xy); ans-= (a[i].x<mn)*(a[i].y+ny);
ans-= (a[i].x>mx)*(a[i].y+xy);
ans%=P;
}
for (int i=st[py];i<y;i++){
ans+= (a[i].x>mn)*(a[i].y+ny);
ans+= (a[i].x<mx)*(a[i].y+xy); ans-= (a[i].x<mn)*(a[i].y+ny);
ans-= (a[i].x>mx)*(a[i].y+xy);
ans%=P; }
for (int i=px+;i<=py-;i++){
ans+= query(i,mn,mx,ny,xy);
ans%=P;
}
}else{
for (int i=x+;i<y;i++){
ans+= (a[i].x>mn)*(a[i].y+ny);
ans+= (a[i].x<mx)*(a[i].y+xy); ans-= (a[i].x<mn)*(a[i].y+ny);
ans-= (a[i].x>mx)*(a[i].y+xy);
}
ans%=P; }
if (x!=y) ans+=a[x].y+a[y].y;
ans%=P;
if (a[x].x>a[y].x) ans=(-ans+P)%P;
printf("%lld\n",lst=(lst+ans+P)%P);
swap(a[x],a[y]);
modify(pos[x]);
modify(pos[y]);
}
return ;
}
另外当块的大小取sqrt(n)/2的时候跑的飞快。。
40s就跑出来了。。竟然有rank5(2017.5.27)。。而且空间也很小有没有。。