@OceanEye7年前
05/2
20:40
看着这道题觉得很神啊
于是写了个n根号nlogn的就开始跑了
然后就跑过去了……
95s的AC
不过写这份代码好像只花了我十分钟？说明我码力还算不错么qwq[单身狗的怨念]
|
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 100010 #define lb(x) (x&-x) int Arr[N]; void add(int x,int v) { while(x<=N) { Arr[x]+=v; x+=lb(x); } } int query(int pos) { int ret=0; while(pos) { ret+=Arr[pos]; pos-=lb(pos); } return ret; } int Arr2[N]; void ins(int x,int v) { while(x<=N) { Arr2[x]+=v; x+=lb(x); } } int _query(int pos) { int ret=0; while(pos) { ret+=Arr2[pos]; pos-=lb(pos); } return ret; } struct rec { int l,r,id; int a,b; }Q[N*10]; #define SIZ 400 int a[N],n,m,cnt[N]; int l[SIZ],r[SIZ],belong[N],SQR,CNT; int ans1[N*10],ans2[N*10]; bool comp(const rec &x,const rec &y) { if(belong[x.l]==belong[y.l]) return x.r<y.r; return x.l<y.l; } void pre() { read(n); read(m); SQR=sqrt(n); CNT=(n-1)/SQR+1; for(int i=1;i<=CNT;++i) { l[i]=(i-1)*SQR+1; r[i]=i*SQR; } r[CNT]=n; for(int i=1;i<=CNT;++i) for(int j=l[i];j<=r[i];++j) belong[j]=i; for(int i=1;i<=n;++i) read(a[i]); for(int i=1;i<=m;++i) { read(Q[i].l); read(Q[i].r); read(Q[i].a); read(Q[i].b); Q[i].id=i; } sort(Q+1,Q+m+1,comp); } int main() { pre(); int nodeL=1,nodeR=0; for(int i=1;i<=m;++i) { while(nodeL>Q[i].l) { nodeL--; add(a[nodeL],1); if(!cnt[a[nodeL]]) ins(a[nodeL],1); cnt[a[nodeL]]++; } while(nodeR<Q[i].r) { nodeR++; add(a[nodeR],1); if(!cnt[a[nodeR]]) ins(a[nodeR],1); cnt[a[nodeR]]++; } while(nodeL<Q[i].l) { add(a[nodeL],-1); cnt[a[nodeL]]--; if(!cnt[a[nodeL]]) ins(a[nodeL],-1); nodeL++; } while(nodeR>Q[i].r) { add(a[nodeR],-1); cnt[a[nodeR]]--; if(!cnt[a[nodeR]]) ins(a[nodeR],-1); nodeR--; } ans1[Q[i].id]=query(Q[i].b)-query(Q[i].a-1); ans2[Q[i].id]=_query(Q[i].b)-_query(Q[i].a-1); } for(int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]); return 0; } |