Created
February 13, 2017 13:17
-
-
Save Ruanxingzhi/7ae4fa86219b2e996e3a3a879c0a45ac to your computer and use it in GitHub Desktop.
【BZOJ3809】Gty的二逼妹子序列
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <cstdlib> | |
| #include <algorithm> | |
| #include <cmath> | |
| #include <vector> | |
| using namespace std; | |
| int n,m,sz; | |
| int a[100005]; | |
| struct ques | |
| { | |
| int l,r,a,b,id; | |
| friend bool operator < (ques a,ques b) | |
| { | |
| return a.r<b.r; | |
| } | |
| }; | |
| vector <ques> q[350]; | |
| void inp() | |
| { | |
| int i; | |
| ques tmp; | |
| scanf("%d%d",&n,&m); | |
| sz=sqrt(n); | |
| for(i=1;i<=n;i++) | |
| scanf("%d",&a[i]); | |
| for(i=0;i<m;i++) | |
| { | |
| scanf("%d%d%d%d",&tmp.l,&tmp.r,&tmp.a,&tmp.b); | |
| tmp.id=i,q[tmp.l/sz].push_back(tmp); | |
| } | |
| } | |
| void pre() | |
| { | |
| int i; | |
| for(i=0;i<sz+5;i++) | |
| sort(q[i].begin(),q[i].end()); | |
| } | |
| struct TA | |
| { | |
| #define MAX 131080 | |
| int bin[MAX+5]; | |
| int lowbit(int x) | |
| { | |
| return x&-x; | |
| } | |
| void ins(int key,int value) | |
| { | |
| int x=key; | |
| while(x<=MAX) | |
| { | |
| bin[x]+=value; | |
| x+=lowbit(x); | |
| } | |
| } | |
| int sum(int l,int r) | |
| { | |
| int i,A=0,B=0; | |
| l--; | |
| while(l) | |
| { | |
| A+=bin[l]; | |
| l-=lowbit(l); | |
| } | |
| while(r) | |
| { | |
| B+=bin[r]; | |
| r-=lowbit(r); | |
| } | |
| return B-A; | |
| } | |
| }; | |
| TA T={0}; | |
| int w[100005]={0}; | |
| int cl=0,cr=0; | |
| void ins(int x) | |
| { | |
| // printf("ins [%d]\n",x); | |
| if(w[a[x]]==0) T.ins(a[x],1); | |
| w[a[x]]++; | |
| } | |
| void del(int x) | |
| { | |
| // printf("del [%d]\n",x); | |
| w[a[x]]--; | |
| if(w[a[x]]==0) T.ins(a[x],-1); | |
| } | |
| void move(int l,int r) | |
| { | |
| while(cl < l) del(cl++); | |
| while(cl > l) ins(--cl); | |
| while(cr < r) ins(++cr); | |
| while(cr > r) del(cr--); | |
| } | |
| int ans[1000005]={0}; | |
| void MO() | |
| { | |
| int i,j; | |
| for(i=0;i<=sz+5;i++) | |
| for(j=0;j<q[i].size();j++) | |
| { | |
| move(q[i][j].l,q[i][j].r); | |
| // printf("[%d,%d] in a[%d,%d] : %d\n",q[i][j].a,q[i][j].b,q[i][j].l,q[i][j].r,ask(q[i][j].a,q[i][j].b)); | |
| ans[q[i][j].id]=T.sum(q[i][j].a,q[i][j].b); | |
| } | |
| for(i=0;i<m;i++) | |
| printf("%d\n",ans[i]); | |
| } | |
| int main(void) | |
| { | |
| inp(); | |
| pre(); | |
| MO(); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment