BZOJ 3236[AHOI2013]作业

题面：

3236: [Ahoi2013]作业

Time Limit: 100 Sec Memory Limit: 512 MB
Submit: 1704 Solved: 685
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3

Sample Output

2 2
1 1
3 2
2 1

HINT

N=100000,M=1000000

离线莫队处理,对权值分块。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define N 100055
 7 #define M 1000066
 8 using namespace std;
 9 int gy[N],be[N],c[M],cc[M],n,m,nn,maxn,tot,num[N];
10 struct Query{
11     int l,r,a,b,id,ans1,ans2;
12 }qr[M];
13 bool cmp1(Query a,Query b){
14     if(be[a.l]==be[b.l])
15         return a.r<b.r;
16     return be[a.l]<be[b.l];
17 }
18 bool cmp2(Query a,Query b){
19     return a.id<b.id;
20 }
21 int lowbit(int x){
22     return x&(-x);
23 }
24 void add(int x,int y){
25     int xx=x;
26     if(y==1&&++num[xx]==1){
27         while(xx<=maxn){
28             cc[xx]++;
29             xx+=lowbit(xx);
30         }
31     }
32     if(y==-1&&--num[xx]==0){
33         while(xx<=maxn){
34             cc[xx]--;
35             xx+=lowbit(xx);
36         }
37     }
38     while(x<=maxn){
39         c[x]+=y;
40         x+=lowbit(x);
41     }
42 }
43 int query(int x){
44     if(x>maxn) x=maxn;
45     int ans=0;
46     while(x){
47         ans+=c[x];
48         x-=lowbit(x);
49     }
50     return ans;
51 }
52 int query1(int x){
53     if(x>maxn) x=maxn;
54     int ans=0;
55     while(x){
56         ans+=cc[x];
57         x-=lowbit(x);
58     }
59     return ans;
60 }
61 void work(){
62     int l=1,r=0;tot=0;
63     for(int i=1;i<=m;i++){
64         while(l<qr[i].l) add(gy[l++],-1);
65         while(l>qr[i].l) add(gy[--l],1);
66         while(r<qr[i].r) add(gy[++r],1);
67         while(r>qr[i].r) add(gy[r--],-1);
68         qr[i].ans1=query(qr[i].b)-query(qr[i].a-1);
69         qr[i].ans2=query1(qr[i].b)-query1(qr[i].a-1);
70     }
71 }
72 int main()
73 {
74     scanf("%d%d",&n,&m); nn=(int)sqrt(n);
75     for(int i=1;i<=n;i++){
76         scanf("%d",&gy[i]);
77         be[i]=(i-1)/nn+1;
78         maxn=max(maxn,gy[i]);
79     }
80     int l,r,a,b;
81     for(int i=1;i<=m;i++){
82         scanf("%d%d%d%d",&l,&r,&a,&b);
83         qr[i].l=l; qr[i].r=r;
84         qr[i].a=a; qr[i].b=b;
85         qr[i].id=i;
86     }
87     sort(qr+1,qr+m+1,cmp1);
88     work();
89     sort(qr+1,qr+m+1,cmp2);
90     for(int i=1;i<=m;i++)
91         printf("%d %d
",qr[i].ans1,qr[i].ans2);
92     return 0;
93 }

BZOJ 3236