好像这道题比小Z的袜(mei)子更简单
要先离散化QAQ
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<string> 7 #include<cmath> 8 #include<ctime> 9 #include<queue> 10 #include<stack> 11 #include<map> 12 #include<set> 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--) 14 #define re(i,l,r) for(int i=(l);i<=(r);i++) 15 #define Clear(a,b) memset(a,b,sizeof(a)) 16 #define inout(x) printf("%d",(x)) 17 #define douin(x) scanf("%lf",&x) 18 #define strin(x) scanf("%s",(x)) 19 #define LLin(x) scanf("%lld",&x) 20 #define op operator 21 #define CSC main 22 typedef unsigned long long ULL; 23 typedef const int cint; 24 typedef long long LL; 25 using namespace std; 26 void inin(int &ret) 27 { 28 ret=0;int f=0;char ch=getchar(); 29 while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} 30 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar(); 31 ret=f?-ret:ret; 32 } 33 int n,m,a[50050],wei[50050]; 34 LL ans[50050],sum; 35 struct que 36 { 37 int l,r,id; 38 void in(int i){inin(l),inin(r),id=i;} 39 bool op < (const que &rhs)const {return wei[l]==wei[rhs.l]?r<rhs.r:l<rhs.l;} 40 }q[50050]; 41 inline int lowbit(int x){return x&-x;} 42 int c[50050]; 43 void add(int x,int a) 44 { 45 while(x<=50000)c[x]+=a,x+=lowbit(x); 46 } 47 int query(int x) 48 { 49 int ret=0; 50 while(x)ret+=c[x],x-=lowbit(x); 51 return ret; 52 } 53 struct wocao 54 { 55 int w,id; 56 bool op < (const wocao &rhs)const {return w<rhs.w;} 57 }w[50050]; 58 bool com(const wocao &a,const wocao &b) 59 { 60 return a.id<b.id; 61 } 62 int CSC() 63 { 64 freopen("in.in","r",stdin); 65 freopen("out.out","w",stdout); 66 inin(n);int nn=sqrt(n); 67 re(i,1,n)inin(w[i].w),w[i].id=i; 68 sort(w+1,w+n+1); 69 re(i,1,n)w[i].w=i; 70 sort(w+1,w+n+1,com); 71 re(i,1,n)a[i]=w[i].w; 72 re(i,1,n)wei[i]=(i-1)/nn+1; 73 inin(m); 74 re(i,1,m)q[i].in(i); 75 sort(q+1,q+m+1); 76 int l=1,r=0; 77 re(i,1,m) 78 { 79 while(r<q[i].r)r++,add(a[r],1),sum+=r-l+1-query(a[r]); 80 while(r>q[i].r)add(a[r],-1),sum-=r-l-query(a[r]),r--; 81 while(l<q[i].l)add(a[l],-1),sum-=query(a[l]-1),l++; 82 while(l>q[i].l)l--,add(a[l],1),sum+=query(a[l]-1); 83 ans[q[i].id]=sum; 84 } 85 re(i,1,m)printf("%lld ",ans[i]); 86 return 0; 87 }