首页 > 代码库 > BZOJ3744: Gty的妹子序列

BZOJ3744: Gty的妹子序列

2024-08-02 06:52:41   220人阅读

3744: Gty的妹子序列

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 111  Solved: 38
[Submit][Status]

Description

我早已习惯你不在身边，
 
人间四月天 寂寞断了弦。
 
回望身后蓝天，
 
跟再见说再见……
 
 
某天,蒟蒻Autumn发现了从 Gty的妹子树(bzoj3720) 上掉落下来了许多妹子,他发现
 
她们排成了一个序列,每个妹子有一个美丽度。
 
Bakser神犇与他打算研究一下这个妹子序列,于是Bakser神犇问道:"你知道区间
 
[l,r]中妹子们美丽度的逆序对数吗?"
 
蒟蒻Autumn只会离线乱搞啊……但是Bakser神犇说道:"强制在线。"
 
请你帮助一下Autumn吧。
 
 
给定一个正整数序列a,对于每次询问,输出al...ar中的逆序对数,强制在线。

 

Input

第一行包括一个整数n(1<=n<=50000),表示数列a中的元素数。
 
第二行包括n个整数a1...an(ai>0,保证ai在int内)。
 
接下来一行包括一个整数m(1<=m<=50000),表示询问的个数。
 
接下来m行,每行包括2个整数l、r(1<=l<=r<=n),表示询问al...ar中的逆序
 
对数(若ai>aj且i<j,则为一个逆序对)。
 
l,r要分别异或上一次询问的答案(lastans),最开始时lastans=0。
 
保证涉及的所有数在int内。

 

Output

对每个询问,单独输出一行,表示al...ar中的逆序对数。

 

Sample Input

4
1 4 2 3
1
2 4

Sample Output

2

HINT

 

Source

By Autumn

 题解：

出题人卡常数丧心病狂。。。

我原来思考过这个问题，还想什么时候出道题呢，结果已经被出出来了。。。

我们分块，然后预处理出i到j块的逆序对数f[i][j]，然后查询的时候不在块内的就暴力查询区间内<或>该数的个数，然后就可以n√n*logn了。。

然后出题人卡常数啊。。。

预处理的时候我偷懒用了主席树结果就T成翔啊。。。

无奈写了BIT。。。

代码：TLE

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 50000+514 #define maxm 1000000+515 #define maxk 500+516 #define eps 1e-1017 #define ll long long18 #define pa pair<int,int>19 #define for0(i,n) for(int i=0;i<=(n);i++)20 #define for1(i,n) for(int i=1;i<=(n);i++)21 #define for2(i,x,y) for(int i=(x);i<=(y);i++)22 #define for3(i,x,y) for(int i=(x);i>=(y);i--)23 #define mod 100000000724 #define l(x) ((x-1)*block+1)25 #define r(x) ((x)==b[n]?n:(x)*block)26 using namespace std;27 inline int read()28 {29     int x=0,f=1;char ch=getchar();30     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}31     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}32     return x*f;33 }34 int n,m,tot,a[maxn],b[maxn],v[maxn],s[maxm],ls[maxm],rs[maxm],rt[maxn],f[maxk][maxk];35 inline bool cmp1(int x,int y){return a[x]<a[y];}36 inline void update(int l,int r,int x,int &y,int z)37 {38     y=++tot;39     s[y]=s[x]+1;40     if(l==r)return;41     ls[y]=ls[x];rs[y]=rs[x];42     int mid=(l+r)>>1;43     if(z<=mid)update(l,mid,ls[x],ls[y],z);else update(mid+1,r,rs[x],rs[y],z);44 }45 inline int query(int x,int y,int z)46 {47     int l=1,r=m,mid,xx=rt[x-1],yy=rt[y],res=0;48     while(l!=r)49     {50         mid=(l+r)>>1;51         if(z<=mid){xx=ls[xx];yy=ls[yy];r=mid;}52         else {res+=s[ls[yy]]-s[ls[xx]];xx=rs[xx];yy=rs[yy];l=mid+1;}53     }54     return res;55 }56 int main()57 {58     freopen("input.txt","r",stdin);59     freopen("output.txt","w",stdout);60     n=read();61     for1(i,n)a[i]=read(),b[i]=i;62     sort(b+1,b+n+1,cmp1);63     for1(i,n)64     {65         if(i==1||(a[b[i]]!=a[b[i-1]]))m++;66         v[b[i]]=m;67     }68     m++;69     for1(i,n)update(1,m,rt[i-1],rt[i],v[i]);70     int block=sqrt(n)*log(n)/log(2);71     for1(i,n)b[i]=(i-1)/block+1;72     for1(i,b[n])73     {74         int tmp=0;75         for2(j,l(i),n)tmp+=(j-l(i)+1)-query(l(i),j,v[j]+1),f[i][b[j]]=tmp;76     }77     int cs=read(),ans=0;78     while(cs--)79     {80         int x=read()^ans,y=read()^ans;if(x>y)swap(x,y);int bx=b[x],by=b[y];81         if(by-bx<2)82         {83             ans=0;84             for2(i,x,y-1)ans+=query(i,y,v[i]);85         }86         else87         {88         ans=f[bx][by];89         for2(i,l(bx),x-1)ans-=query(i,r(by),v[i]);90         for2(i,y+1,r(by))ans-=i-x+1-query(x,i,v[i]+1);91         }92         printf("%d\n",ans);93     }94     return 0;95 }
View Code

17s

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 50000+5 14 #define maxm 3000000+5 15 #define maxk 1000+5 16 #define eps 1e-10 17 #define ll long long 18 #define pa pair<int,int> 19 #define for0(i,n) for(int i=0;i<=(n);i++) 20 #define for1(i,n) for(int i=1;i<=(n);i++) 21 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 22 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 23 #define mod 1000000007 24 #define l(x) ((x-1)*block+1) 25 #define r(x) ((x)==b[n]?n:(x)*block) 26 using namespace std; 27 inline int read() 28 { 29     int x=0,f=1;char ch=getchar(); 30     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 31     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 32     return x*f; 33 } 34 int n,m,tot,a[maxn],b[maxn],v[maxn],s[maxm],ss[maxn],ls[maxm],rs[maxm],rt[maxn],f[maxk][maxk]; 35 inline bool cmp1(int x,int y){return a[x]<a[y];} 36 inline void update(int l,int r,int x,int &y,int z) 37 { 38     y=++tot; 39     s[y]=s[x]+1; 40     if(l==r)return; 41     ls[y]=ls[x];rs[y]=rs[x]; 42     int mid=(l+r)>>1; 43     if(z<=mid)update(l,mid,ls[x],ls[y],z);else update(mid+1,r,rs[x],rs[y],z); 44 } 45 inline int query(int x,int y,int z) 46 { 47     int l=1,r=m,mid,xx=rt[x-1],yy=rt[y],res=0; 48     while(l!=r) 49     { 50         mid=(l+r)>>1; 51         if(z<=mid){xx=ls[xx];yy=ls[yy];r=mid;} 52         else {res+=s[ls[yy]]-s[ls[xx]];xx=rs[xx];yy=rs[yy];l=mid+1;} 53     } 54     return res; 55 } 56 inline int sum(int x){int t=0;for(;x;x-=x&(-x))t+=ss[x];return t;} 57 inline void add(int x,int y){for(;x<=m;x+=x&(-x))ss[x]+=y;}  58 int main() 59 { 60     freopen("input.txt","r",stdin); 61     freopen("output.txt","w",stdout); 62     n=read(); 63     for1(i,n)a[i]=read(),b[i]=i; 64     sort(b+1,b+n+1,cmp1); 65     for1(i,n) 66     { 67         if(i==1||(a[b[i]]!=a[b[i-1]]))m++; 68         v[b[i]]=m; 69     } 70     m++; 71     for1(i,n)update(1,m,rt[i-1],rt[i],v[i]); 72     int block=sqrt(n); 73     for1(i,n)b[i]=(i-1)/block+1; 74     for1(i,b[n]) 75     { 76         int tmp=0; 77         for2(j,l(i),n) 78         { 79          add(v[j],1); 80          tmp+=j-l(i)+1-sum(v[j]); 81          f[i][b[j]]=tmp; 82         } 83         for2(j,l(i),n)add(v[j],-1); 84     } 85     //for1(i,b[n])for1(j,b[n])cout<<i<<‘ ‘<<j<<‘ ‘<<f[i][j]<<endl; 86     int cs=read(),ans=0; 87     while(cs--) 88     { 89         int x=read()^ans,y=read()^ans;if(x>y)swap(x,y);int bx=b[x],by=b[y]; 90         if(by-bx<2) 91         { 92             ans=0; 93             for2(i,x,y-1)ans+=query(i,y,v[i]); 94         } 95         else 96         { 97         ans=f[bx][by]; 98         for2(i,l(bx),x-1)ans-=query(i,r(by),v[i]); 99         for2(i,y+1,r(by))ans-=i-x+1-query(x,i,v[i]+1);100         }101         printf("%d\n",ans);102     }103     return 0;104 }
View Code

20s

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 50000+5 14 #define maxm 3000000+5 15 #define maxk 1000+5 16 #define eps 1e-10 17 #define ll long long 18 #define pa pair<int,int> 19 #define for0(i,n) for(int i=0;i<=(n);i++) 20 #define for1(i,n) for(int i=1;i<=(n);i++) 21 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 22 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 23 #define mod 1000000007 24 #define l(x) ((x-1)*block+1) 25 #define r(x) ((x)==b[n]?n:(x)*block) 26 using namespace std; 27 inline int read() 28 { 29     int x=0,f=1;char ch=getchar(); 30     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 31     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 32     return x*f; 33 } 34 int n,m,tot,a[maxn],b[maxn],v[maxn],s[maxm],ss[maxn],ls[maxm],rs[maxm],rt[maxn],f[maxk][maxk]; 35 inline bool cmp1(int x,int y){return a[x]<a[y];} 36 inline void update(int l,int r,int x,int &y,int z) 37 { 38     y=++tot; 39     s[y]=s[x]+1; 40     if(l==r)return; 41     ls[y]=ls[x];rs[y]=rs[x]; 42     int mid=(l+r)>>1; 43     if(z<=mid)update(l,mid,ls[x],ls[y],z);else update(mid+1,r,rs[x],rs[y],z); 44 } 45 inline int query(int x,int y,int z) 46 { 47     int l=1,r=m,mid,xx=rt[x-1],yy=rt[y],res=0; 48     while(l!=r) 49     { 50         mid=(l+r)>>1; 51         if(z<=mid){xx=ls[xx];yy=ls[yy];r=mid;} 52         else {res+=s[ls[yy]]-s[ls[xx]];xx=rs[xx];yy=rs[yy];l=mid+1;} 53     } 54     return res; 55 } 56 inline int sum(int x){int t=0;for(;x;x-=x&(-x))t+=ss[x];return t;} 57 inline void add(int x,int y){for(;x<=m;x+=x&(-x))ss[x]+=y;}  58 int main() 59 { 60     freopen("input.txt","r",stdin); 61     freopen("output.txt","w",stdout); 62     n=read(); 63     for1(i,n)a[i]=read(),b[i]=i; 64     sort(b+1,b+n+1,cmp1); 65     for1(i,n) 66     { 67         if(i==1||(a[b[i]]!=a[b[i-1]]))m++; 68         v[b[i]]=m; 69     } 70     m++; 71     for1(i,n)update(1,m,rt[i-1],rt[i],v[i]); 72     int block=sqrt(n); 73     for1(i,n)b[i]=(i-1)/block+1; 74     for1(i,b[n]) 75     { 76         int tmp=0; 77         for2(j,l(i),n) 78         { 79          add(v[j],1); 80          tmp+=j-l(i)+1-sum(v[j]); 81          f[i][b[j]]=tmp; 82         } 83         for2(j,l(i),n)add(v[j],-1); 84     } 85     //for1(i,b[n])for1(j,b[n])cout<<i<<‘ ‘<<j<<‘ ‘<<f[i][j]<<endl; 86     int cs=read(),ans=0; 87     while(cs--) 88     { 89         int x=read()^ans,y=read()^ans;if(x>y)swap(x,y);int bx=b[x],by=b[y]; 90         if(by-bx<2) 91         { 92             ans=0; 93             for2(i,x,y-1)ans+=query(i,y,v[i]); 94         } 95         else 96         { 97         ans=f[bx+1][by-1]; 98         for2(i,x,r(bx))ans+=query(i,r(by-1),v[i]); 99         for2(i,l(by),y)ans+=i-x+1-query(x,i,v[i]+1);100         }101         printf("%d\n",ans);102     }103     return 0;104 }
View Code

 

BZOJ3744: Gty的妹子序列


联系
我们