首页 > 代码库 > BZOJ 3236: [Ahoi2013]作业

BZOJ 3236: [Ahoi2013]作业

2024-08-05 09:06:45   216人阅读

题目

3236: [Ahoi2013]作业

Time Limit: 100 Sec  Memory Limit: 512 MB
Submit: 732  Solved: 271

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

 

Source

By wangyisong1996加强数据

 

题解

一道卡测评的好题！用传说的莫队算法能水过，就是我们把每个询问x0,y0看作平面上的一个点，那么暴力转移的代价就是两个点之间的距离，我们把x轴分块，这样总的转移的代价和就是O(sqrt(n)*n)的了。由于这道题需要树状数组维护一下，所以这题的复杂度是O(nsqrt(n)logn)的。

代码

  1 /*Author:WNJXYK*/  2 #include<cstdio>  3 #include<algorithm>  4 using namespace std;  5   6 const int Maxm=1000000;  7 struct QuestionNode{  8     int l,r;  9     int a,b; 10     int index; 11 };  12 QuestionNode quest[Maxm+10]; 13 struct AnsNode{ 14     int Ans1,Ans2; 15 }; 16 AnsNode ans[Maxm+10]; 17  18 const int Maxn=100000; 19 int cnt[Maxn+10]; 20  21 int siz; 22 int n,m; 23 int num[Maxn+10]; 24  25 int sum1[Maxn+10],sum2[Maxn+10],cot[Maxn+10];  26  27 inline int remin(int a,int b){ 28     if (a<b) return a; 29     return b; 30 } 31  32 inline bool cmp(QuestionNode a,QuestionNode b){ 33     if (cnt[a.l]<cnt[b.l]) return true; 34     if (cnt[a.l]==cnt[b.l] && a.r<b.r) return true; 35     return false; 36 } 37  38 inline int lowbit(int x){ 39     return x&-x; 40 } 41  42 inline void add(int c[],int x,int num){ 43     for (int i=x;i<=Maxn;i+=lowbit(i))c[i]+=num; 44 } 45  46 inline int get(int c[],int x){ 47     int res=0; 48     for (int i=x;i;i-=lowbit(i))res+=c[i]; 49     return res; 50 } 51  52 int main(){ 53     scanf("%d%d",&n,&m); 54     //GetCnt 55     while(siz*siz<n) siz++; 56     for (int i=1;i<=siz;i++){ 57         int st=siz*(i-1)+1,ed=(remin(siz*i,n)); 58         for (int j=st;j<=ed;j++){ 59             cnt[j]=i; 60         } 61     }     62     //GetNum 63     for (int i=1;i<=n;i++) scanf("%d",&num[i]); 64     //GetQuest 65     for (int i=1;i<=m;i++)scanf("%d%d%d%d",&quest[i].l,&quest[i].r,&quest[i].a,&quest[i].b); 66     for (int i=1;i<=m;i++)quest[i].index=i; 67     //SortQuest 68     sort(quest+1,quest+m+1,cmp); 69     //GetAns 70     int left=1,right=0; 71     for (int i=1;i<=m;i++){ 72         int l=quest[i].l,r=quest[i].r; 73         int a=quest[i].a,b=quest[i].b; 74         int index=quest[i].index; 75         while (left<l){ 76             cot[num[left]]--; 77             add(sum1,num[left],-1); 78             if (cot[num[left]]==0) add(sum2,num[left],-1); 79             left++; 80         } 81         while(l<left){ 82             left--; 83             cot[num[left]]++; 84             add(sum1,num[left],1); 85             if (cot[num[left]]==1) add(sum2,num[left],1); 86         } 87         while(right<r){ 88             right++; 89             cot[num[right]]++; 90             add(sum1,num[right],1); 91             if (cot[num[right]]==1) add(sum2,num[right],1); 92         } 93         while(r<right){ 94             cot[num[right]]--; 95             add(sum1,num[right],-1); 96             if (cot[num[right]]==0) add(sum2,num[right],-1); 97             right--; 98         } 99         ans[index].Ans1=get(sum1,b)-get(sum1,a-1);100         ans[index].Ans2=get(sum2,b)-get(sum2,a-1);101     }102     //Print103     for (int i=1;i<=m;i++) printf("%d %d\n",ans[i].Ans1,ans[i].Ans2);104     return 0;105 }
View Code

 

BZOJ 3236: [Ahoi2013]作业


联系
我们