Time Limit: 40 Sec (Total)
Memory Limit: 128 MB
莫队+树状数组维护
类(jiu)似(shi)冒泡排序的过程
注意优化时间
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<cstdlib> #include<algorithm> #include<iterator> using namespace std; int n,m,seq[100010]={0},fwt[100010]={0},setx[100010]={0},blksz=0,setlen=0; struct asksx { int codex,lx,rx,ans; }ask[100010]={0}; int nowans=0; inline void readx(int& x) { x=0; int k=1; register char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } inline int BinSearch(int val) { int l=1,r=setlen,mid; while (1) { mid=(l+r)>>1; if (setx[mid]==val) return mid; else if (setx[mid]>val) r=mid-1; else l=mid+1; } } inline void process1() { setlen=n; memcpy(setx,seq,sizeof(seq)); sort(setx+1,setx+n+1); for (int i=1;i<=n;i++) if (setx[i]==setx[i+1]) { setx[i]=2*1e9; setlen--; } sort(setx+1,setx+n+1); for (int i=1;i<=n;i++) seq[i]=BinSearch(seq[i]); } inline bool cmp1(asksx a,asksx b) { if ((a.lx/blksz)==(b.lx/blksz)) return a.rx<b.rx; else return a.lx<b.lx; } inline bool cmp2(asksx a,asksx b) { return a.codex<b.codex; } inline void update(int pos,int val) { while (pos<=setlen) { fwt[pos]+=val; pos+=(pos&(-pos)); } } inline int query(int pos) { int sum=0; while (pos) { sum+=fwt[pos]; pos-=(pos&(-pos)); } return sum; } int main() { readx(n); blksz=sqrt(n); for (int i=1;i<=n;i++) readx(seq[i]); readx(m); for (int i=1;i<=m;i++) { ask[i].codex=i; readx(ask[i].lx); readx(ask[i].rx); } process1(); sort(ask+1,ask+m+1,cmp1); int lpos=1,rpos=0; for (int i=1;i<=m;i++) { while (rpos<ask[i].rx) { rpos++; update(seq[rpos],1); nowans+=(query(setlen)-query(seq[rpos])); } while (rpos>ask[i].rx) { update(seq[rpos],-1); nowans-=(query(setlen)-query(seq[rpos])); rpos--; } while (lpos<ask[i].lx) { update(seq[lpos],-1); nowans-=query(seq[lpos]-1); lpos++; } while (lpos>ask[i].lx) { lpos--; update(seq[lpos],1); nowans+=query(seq[lpos]-1); } ask[i].ans=nowans; } sort(ask+1,ask+m+1,cmp2); for (int i=1;i<=m;i++) printf("%d\n",ask[i].ans); return 0; } |