ACdream 1738 世风日下的哗啦啦族I(分块)

世风日下的哗啦啦族I(分块)"/>

ACdream 1738 世风日下的哗啦啦族I(分块)

题意：给出一个序列三种操作
1 a b
修改a妹子的裙子，变成b长度
2 l r
查询[l,r]区间的妹子最短的裙子长度，并输出有多少个妹子穿这个长度裙子的
3 l r t
输出[l,r]区间的妹子身穿裙子长度小于等于t的个数

暴力分块，优化一下了二分

#include<cstring>
#include<string>
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
//#pragma comment(linker, "/STACK:1024000000,1024000000");using namespace std;#define INF 0x3f3f3f3f
#define maxn 50005int n,m;
int a[maxn];
int block,num,belong[maxn],l[maxn],r[maxn],minn[maxn];
vector<int>Q[250];void init()
{block=sqrt(n);num=n/block;if(n%block) num++;for(int i=1; i<=n; i++){belong[i]=(i-1)/block+1;Q[belong[i]].push_back(a[i]);}for(int i=1; i<=num; i++){l[i]=(i-1)*block+1;r[i]=i*block;sort(Q[i].begin(),Q[i].end());minn[i]=0;for(int j=l[i]; j<=r[i]; j++){if(a[j]==Q[i][0]) minn[i]++;}}r[num]=n;
}void update(int x,int y)
{a[x]=y;Q[belong[x]].clear();for(int i=l[belong[x]]; i<=r[belong[x]]; i++){Q[belong[x]].push_back(a[i]);}sort(Q[belong[x]].begin(),Q[belong[x]].end());minn[belong[x]]=0;for(int i=l[belong[x]]; i<=r[belong[x]]; i++){if(Q[belong[x]][0]==a[i]) minn[belong[x]]++;}
}void query1(int x,int y)
{int ans=INF;if(belong[x]==belong[y]){for(int i=x; i<=y; i++){ans=min(a[i],ans);}}else{for(int i=x; i<=r[belong[x]]; i++){ans=min(ans,a[i]);}for(int i=belong[x]+1; i<belong[y]; i++){ans=min(ans,Q[i][0]);}for(int i=l[belong[y]]; i<=y; i++){ans=min(ans,a[i]);}}int ans2=0;if(belong[x]==belong[y]){for(int i=x; i<=y; i++){if(a[i]==ans) ans2++;}}else{for(int i=x; i<=r[belong[x]]; i++){if(a[i]==ans) ans2++;}for(int i=belong[x]+1; i<belong[y]; i++){if(Q[i][0]==ans)ans2+=minn[i];}for(int i=l[belong[y]]; i<=y; i++){if(a[i]==ans) ans2++;}}printf("%d %d\n",ans,ans2);
}int query2(int x,int y,int c)
{int ans=0;if(belong[x]==belong[y]){for(int i=x; i<=y; i++){if(a[i]<=c) ans++;}}else{for(int i=x; i<=r[belong[x]]; i++){if(a[i]<=c) ans++;}for(int i=belong[x]+1; i<belong[y]; i++){int pos=upper_bound(Q[i].begin(),Q[i].end(),c)-Q[i].begin();ans+=pos;}for(int i=l[belong[y]]; i<=y; i++){if(a[i]<=c) ans++;}}return ans;
}int main()
{while(scanf("%d%d",&n,&m)!=EOF){for(int i=1; i<=n; i++){scanf("%d",&a[i]);}init();while(m--){int op;scanf("%d",&op);if(op==1){int x,y;scanf("%d%d",&x,&y);update(x,y);}else if(op==2){int x,y;scanf("%d%d",&x,&y);query1(x,y);}else{int x,y,c;scanf("%d%d%d",&x,&y,&c);printf("%d\n",query2(x,y,c));}}for(int i=1; i<=num; i++) Q[i].clear();}return 0;
}