3295: [Cqoi2011]動態逆序對 Description 對於序列A，它的逆序對數定義為滿足i<j，且Ai>Aj的數對(i,j)的個數。 給1到n的一個排列，按照某種順序依次刪除m個元素。 你的任務是在每次刪除一個元素之前統計整個序列的逆序對數。 對於序列A，它的逆序對數定義為滿足i<j， ...
3295: [Cqoi2011]動態逆序對
Time Limit: 10 Sec Memory Limit: 128 MBDescription
對於序列A，它的逆序對數定義為滿足i<j，且Ai>Aj的數對(i,j)的個數。 給1到n的一個排列，按照某種順序依次刪除m個元素。 你的任務是在每次刪除一個元素之前統計整個序列的逆序對數。Input
輸入第一行包含兩個整數n和m，即初始元素的個數和刪除的元素個數。 以下n行每行包含一個1到n之間的正整數，即初始排列。 以下m行每行一個正整數，依次為每次刪除的元素。Output
輸出包含m行，依次為刪除每個元素之前，逆序對的個數。Sample Input
5 41 5 3 4 2
5 1 4 2
Sample Output
52
2
1
樣例解釋
(1,5,3,4,2) (1,3,4,2) (3,4,2) (3,2) (3)。
HINT
N<=100000 M<=50000
表示當時沒看出來是CDQ，樹套樹倒是瞄出來了，只是不會寫啊。
現在看來還是很顯然的。
對於排列中的數，記它被刪除的時間為t(未刪除的設為m+1)，下標為X，大小為Y。
那麼對於一個數i，來看在它前面被刪除的數對它的答案的減小值為多少：
Σ(Tj<Ti && Xj<Xi && Yj>Yi) + Σ(Tj<Ti && Xj>Xi && Yj<Yi)
做兩次CDQ就好了。這種沒有重覆的算起來真是爽啊。
做的時候沒有草稿紙真TM不爽。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 100010;
struct Data{
int X,Y,T;long long len;
bool operator <(const Data &t)const{
return T<t.T;
}
}rem[N],f[N],t[N];
int n,m,ban[N],bplace[N],A[N],T[N];
long long Ans,ans[N];
inline int gi()
{
int x=0,res=1;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')res=-res;ch=getchar();}
while(ch>'/' && ch<':')x=x*10+ch-48,ch=getchar();
return x*res;
}
inline int lb(int k){return k&-k;}
inline void update(int x){for(;x<=n;x+=lb(x))T[x]++;}
inline int query(int x)
{
int ans=0;
for(;x;x-=lb(x))ans+=T[x];
return ans;
}
inline void clean(int x){for(;x<=n;x+=lb(x))T[x]=0;}
inline void calc()
{
memset(T,0,sizeof(T));Ans=0;
for(int i=1;i<=n;++i){
Ans+=(i-query(A[i])-1);
update(A[i]);
}
memset(T,0,sizeof(T));
}
//在外面保證T有序，CDQ內保證X有序，統計Y值。
//T：時間 X：位置 Y：權值
//CDQ calc Ti<Tj Xi<Xj Y[i]<Y[j]
inline void CDQ(int l,int r)
{
if(l==r)return;int mid=(l+r)>>1;
CDQ(l,mid);CDQ(mid+1,r);
int x=l,y=mid+1,z=l;
while(x<=mid && y<=r)
if(f[x].X<f[y].X)update(f[x].Y),t[z++]=f[x++];
else f[y].len+=query(f[y].Y),t[z++]=f[y++];
while(x<=mid)t[z++]=f[x++];
while(y<=r)f[y].len+=query(f[y].Y),t[z++]=f[y++];
for(int i=l;i<=mid;++i)clean(f[i].Y);
for(int i=l;i<=r;++i)f[i]=t[i];
}
int main()
{
n=gi();m=gi();
for(int i=1;i<=n;++i)
A[i]=gi();
for(int i=1;i<=m;++i)
bplace[ban[i]=gi()]=i;
for(int i=1;i<=n;++i){
rem[i].T=bplace[A[i]];
rem[i].X=i;
rem[i].Y=A[i];
if(!rem[i].T)rem[i].T=m+1;
}
sort(rem+1,rem+n+1);calc();
for(int i=0;i<=m;++i)ans[i]=Ans;
for(int i=1;i<=n;++i){
f[i]=rem[i];
f[i].Y=n-f[i].Y+1;
}
reverse(f+1,f+n+1);
CDQ(1,n);sort(f+1,f+n+1);
for(long long i=1,s=0;i<=n;++i){
if(!f[i].T)continue;
ans[f[i].T]-=s;s+=f[i].len;
}
for(int i=1;i<=n;++i){
f[i]=rem[i];
f[i].X=n-f[i].X+1;
}
reverse(f+1,f+n+1);
CDQ(1,n);sort(f+1,f+n+1);
for(long long i=1,s=0;i<=n;++i){
if(!f[i].T)continue;
ans[f[i].T]-=s;s+=f[i].len;
}
for(int i=1;i<=m;++i)
printf("%lld\n",ans[i]);
return 0;
}
然後看見我在上古時期的分塊？？！！
一臉懵逼。
瞪了好久發現 不是我寫的。
大概思想就是分塊，每塊內排序。
然後查詢：
不在自己塊里的，二分一下。
在自己塊里的，暴力搞搞。
然後刪掉。
6000ms...過去了...
昂波利污波。
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
const int N=200050;
int n,m,a[N];
int tmp[N],t[N];//merge-sort
int belong[N],L[N],R[N],cnt,k,x,y;
int ad[N]; //i在原數列中的位置為ad[i]
int b[N]; //每個塊維護有序數列
int sum[N]; //當前塊中刪除了多少個數
int adx;
int i;
bool f[N];
ll tot; //當前逆序對數 開 long long !
inline int get(){
int p=0;char x=getchar();
while (x<'0' || x>'9') x=getchar();
while (x>='0' && x<='9') p=p*10+x-'0',x=getchar();
return p;
}
inline void merge_sort(int l,int r){
int mid,p,i,j;
mid=(l+r)>>1;
i=p=l;j=mid+1;
while (i<=mid && j<=r)
if (tmp[i]>tmp[j]) t[p++]=tmp[j++],tot+=mid-i+1;
else t[p++]=tmp[i++];
while (i<=mid) t[p++]=tmp[i++];
while (j<=r) t[p++]=tmp[j++];
for (i=l;i<=r;i++) tmp[i]=t[i];
return ;
}
inline void merge(int l,int r){
if (l>=r) return ;
int mid=(l+r)>>1;
merge(l,mid);
merge(mid+1,r);
merge_sort(l,r);
return ;
}
void init(){
n=get();m=get();
k=sqrt(n); //塊大小
cnt=n/k;if (n%k) cnt++; //塊個數
for (int i=1;i<=n;i++)
a[i]=get(),ad[a[i]]=i,belong[i]=(i-1)/k+1;
for (int i=1;i<=cnt;i++)
L[i]=i*k-k+1,R[i]=i*k;
R[cnt]=n;
memcpy(tmp,a,sizeof tmp);
tot=0;
merge(1,n);
memcpy(b,a,sizeof a);
for (int i=1;i<=cnt;i++)
sort(b+L[i],b+R[i]+1);
memset(f,1,sizeof f);
return ;
}
inline int search(int t,int p){
int l,r,ret;
l=L[t]; r=R[t]; ret=R[t];
while (l<=r){
int mid=(l+r)>>1;
if (b[mid]<=p) ret=mid,l=mid+1;
else r=mid-1;
}
if (b[ret]>p) ret=L[i]-1;
return ret;
}
int main(){
init();
for (int p=1;p<=m;p++){
printf("%lld\n",tot);
y=get();x=ad[y]; //得到在a數列中的位置 所處的塊的編號肯定不變
k=belong[x]; //x屬於第k個塊
for (i=1;i<k;i++)
tot-=R[i]-search(i,a[x]);
for (i=k+1;i<=cnt;i++)
tot-=search(i,a[x])-L[i]+1-sum[i];
for (i=L[k];i<x;i++)
if (f[a[i]] && a[i]>a[x]) tot--;
for (i=x+1;i<=R[k];i++)
if (f[a[i]] && a[i]<a[x]) tot--;
adx=search(k,a[x]);
b[adx]=0;sum[k]++;
f[a[x]]=0;
sort(b+L[k],b+R[k]+1);
}
return 0;
}
