题目链接
https://vjudge.net/problem/204321/origin
题目
“世风日下啊，女生不穿裙子的太少了”
“这不是社会的进步吗（逃”
“哎，是否可以建立一种结构统计一下各学院各专业各班级女生穿裙子的数量以及裙子的长度”
“然后查询区间裙子最短值?”
“并输出这个区间 穿这个裙子长度的妹子 有多少个?”
“然后判断下在有风的情况下，多少妹子是安全的.”
“maya 哗啦啦族真是太可怕啦！”
Input
第一行 n,m表示n个妹子，m个操作
第二行 a1 a2 a3 …… an，n个整数，表示妹子一开始的裙子长度
下面m行：
总共3种操作
1 a b
修改a妹子的裙子，变成b长度
2 l r
查询[l,r]区间的妹子最短的裙子长度，并输出有多少个妹子穿这个长度裙子的
3 l r t
输出[l,r]区间的妹子身穿裙子长度小于等于t的个数
1<=n,m<=50000
1<=a<=n
1<=b<=50000
1<=ai<=50000
1<=l<=r<=n
0<=t<=50000
Output
根据询问，输出答案
询问为2 则在一行输出两个整数 a b
询问为3 则只输出一个整数c
Sample Input
3 3
1 2 3
1 1 4
2 1 3
3 1 3 2
Sample Output
2 1
1
解题
分块。
分成sqrt（n）块，块内进行排序。
对于操作1，维护原数组和分块有序数组。
对于操作2，非成块的，暴力去找；成块的，根据块内有序去进行二分。
对于操作3，同2.
代码
ACdream暂时交不了。
我感觉思路没错。就先贴代码吧。
样例过了就当它过了吧= =。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;const int maxn=5e4+7;
int n,m,a[maxn];
int belong[maxn],l[maxn],r[maxn],num,block;
int d[maxn];void build()
{block=(int)sqrt(n+0.5);num=n/block;if(n%block) num++;for(int i=1;i<=n;i++){belong[i]=(i-1)/block+1;d[i]=a[i];}for(int i=1;i<=num;i++){l[i]=(i-1)*block+1;r[i]=i*block;}r[num]=n;for(int i=1;i<=num;i++)sort(d+l[i],d+r[i]+1);
}
void update(int x,int y)
{a[x]=y;for(int i=l[belong[x]];i<=r[belong[x]];i++)d[i]=a[i];sort(d+l[belong[x]],d+r[belong[x]]+1);
}
void query(int x,int y)
{int ans=INF,sum=0;if(belong[x]==belong[y]){for(int i=x;i<=y;i++)ans=min(ans,a[i]);for(int i=x;i<=y;i++)if(a[i]==ans) sum++;printf("%d %d\n",ans,sum);return ;}for(int i=x;i<=r[belong[x]];i++)ans=min(ans,a[i]);for(int i=l[belong[y]];i<=y;i++)ans=min(ans,a[i]);for(int i=belong[x]+1;i<belong[y];i++)ans=min(ans,d[l[i]]);for(int i=x;i<=r[belong[x]];i++)if(a[i]==ans) sum++;for(int i=l[belong[y]];i<=y;i++)if(a[i]==ans) sum++;for(int i=belong[x]+1;i<belong[y];i++){int ll=lower_bound(d+l[i],d+r[i]+1,ans)-(d+l[i]);int rr=upper_bound(d+l[i],d+r[i]+1,ans)-(d+l[i]);int tmp=rr-ll;// printf("tmp=%d %d\n",ll,rr);sum+=tmp;}printf("%d %d\n",ans,sum);return ;
}
void out(int x,int y,int t)
{int ans=0;if(belong[x]==belong[y]){for(int i=x;i<=y;i++)if(a[i]<=t) ans++;printf("%d\n",ans);return ;}for(int i=x;i<=r[belong[x]];i++)if(a[i]<=t) ans++;for(int i=l[belong[y]];i<=y;i++)if(a[i]<=t) ans++;for(int i=belong[x]+1;i<belong[y];i++){int tmp=upper_bound(d+l[i],d+r[i]+1,t)-(d+l[i]);ans+=tmp;}printf("%d\n",ans);return ;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]==-1) a[i]=INF;}build();while(m--){int op,x,y,t;scanf("%d",&op);if(op==1){scanf("%d%d",&x,&y);update(x,y);}else if(op==2){scanf("%d%d",&x,&y);query(x,y);}else{scanf("%d%d%d",&x,&y,&t);out(x,y,t);}}return 0;
}