首页 > 代码库 > 【莫队算法】bzoj3289 Mato的文件管理
【莫队算法】bzoj3289 Mato的文件管理
莫队算法，离线回答询问，按一定大小(sqrt(n*log(n))左右)将答案分块，按 ①左端点所在块②右端点 双关键字排序。
然后暴力转移。
转移的时候用树状数组。
O(n*sqrt(n)*log(n))。
注意：①在一列数的后面添加一个数，逆序对数会增加 数列中比它大的数的个数。
②在一列数的后面删除一个数，逆序对数会减少 数列中比它大的数的个数。
③在一列数的前面添加一个数，逆序对数会增加 数列中比它小的数的个数。
④在一列数的前面删除一个数，逆序对数会减少 数列中比它小的数的个数。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 using namespace std; 5 struct Point{int x,y;}a[50001]; 6 struct ASK{int l,r,lb,p;}Q[50001]; 7 bool operator < (const ASK &a,const ASK &b){return a.lb!=b.lb ? a.lb<b.lb : a.r<b.r;} 8 bool operator < (const Point &a,const Point &b){return a.x<b.x;} 9 int n,m,sz,sum,num[50001],b[50001],cnt; 10 int d[50001],ans[50001],res; 11 inline int lowbit(const int &x){return x&(-x);} 12 inline void add(int p,const int &x){while(p<=n){d[p]+=x;p+=lowbit(p);}} 13 inline int getsum(int p){int res=0;while(p){res+=d[p];p-=lowbit(p);}return res;} 14 int Res,Num;char C,CH[12]; 15 inline int G() 16 { 17 Res=0;C=‘*‘; 18 while(C<‘0‘||C>‘9‘)C=getchar(); 19 while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();} 20 return Res; 21 } 22 inline void P(long long x) 23 { 24 Num=0;if(!x){putchar(‘0‘);puts("");return;} 25 while(x>0)CH[++Num]=x%10,x/=10; 26 while(Num)putchar(CH[Num--]+48); 27 puts(""); 28 } 29 void makeblock() 30 { 31 sz=sqrt((double)n*4.6); int L,R; 32 for(sum=1;sum*sz<n;sum++) 33 { 34 L=(sum-1)*sz+1; R=sum*sz; 35 for(int i=L;i<=R;i++) num[i]=sum; 36 } 37 L=sz*(sum-1)+1; R=n; 38 for(int i=L;i<=R;i++) num[i]=sum; 39 } 40 void LiSan() 41 { 42 int en=1; sort(a+1,a+n+1); b[a[1].y]=1; 43 for(int i=2;i<=n;i++) 44 { 45 if(a[i].x!=a[i-1].x) en++; 46 b[a[i].y]=en; 47 } 48 } 49 int main() 50 { 51 n=G(); 52 for(int i=1;i<=n;i++) 53 { 54 a[i].x=G(); 55 a[i].y=i; 56 } 57 makeblock(); LiSan(); m=G(); 58 for(int i=1;i<=m;i++) 59 { 60 Q[i].l=G(); Q[i].r=G(); 61 Q[i].lb=num[Q[i].l]; 62 Q[i].p=i; 63 } 64 sort(Q+1,Q+m+1); 65 for(int i=Q[1].l;i<=Q[1].r;i++) 66 { 67 cnt++; 68 add(b[i],1); 69 res+=(cnt-getsum(b[i])); 70 } ans[Q[1].p]=res; 71 for(int i=2;i<=m;i++) 72 { 73 if(Q[i].l<Q[i-1].l) 74 { 75 for(int j=Q[i-1].l-1;j>=Q[i].l;j--) 76 { 77 res+=getsum(b[j]-1); 78 add(b[j],1); 79 } 80 cnt+=(Q[i-1].l-Q[i].l); 81 } 82 else 83 { 84 for(int j=Q[i-1].l;j<Q[i].l;j++) 85 { 86 res-=getsum(b[j]-1); 87 add(b[j],-1); 88 } 89 cnt-=(Q[i].l-Q[i-1].l); 90 } 91 if(Q[i].r<Q[i-1].r) 92 { 93 for(int j=Q[i-1].r;j>Q[i].r;j--) 94 { 95 res-=(cnt-getsum(b[j])); 96 cnt--; 97 add(b[j],-1); 98 } 99 }100 else101 {102 for(int j=Q[i-1].r+1;j<=Q[i].r;j++)103 {104 cnt++;105 add(b[j],1);106 res+=(cnt-getsum(b[j]));107 }108 }109 ans[Q[i].p]=res;110 }111 for(int i=1;i<=m;i++) P(ans[i]);112 return 0;113 }
【莫队算法】bzoj3289 Mato的文件管理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。