题解：P14397 [JOISC 2016] 雇佣计划 / Employment
注：本题解使用的分块方法，若是想学习更加无比简单的更加快速的树状数组方法请移步。虽然感觉分块更加无脑。
首先发现和第十分块咋这么像呢，和第十分块几乎一样的操作。但是这题是全局查询并不需要序列分块，而且修改超级好写。尽管ATRI宝宝因为莫名原因调了几个小时。
一样的思路，假如没有修改我们可以怎么做。先思考维护的是什么，对于我们每次询问的
可是您咋带修。所以我们操作分块。
首先将读入的数离散化，然后对操作分块。每个块内操作单独处理。每个块内询问按
这个做法显然可以拓展到区间询问，只需要往里面塞一个序列分块。
但是不知道为什么，我的这个做法块长直接取
另外写完了可以继续去写第十分块。
::::success[code]
/*
——我们的时间，就这样开始了。
海风吹拂着面颊……纯白色的羽毛从天空中降下。
我们手牵着手仰望着天空，立下要去恋爱的誓言————
*/
#include<bits/stdc++.h>
//#pragma GCC optimize(1,2,3,"Ofast","inline")
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define int long long
using namespace std;
inline int read(){
int x=0;char ch=getchar();
int f=1;
for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
struct node{int opt,x,y,z;}qs[200010];
struct node1{int x,t,id;}b[600];
struct node2{int x,y,z;}c[600];
int lenb,lenc;
struct node4{
int id1,id2,x,k;
}dyz[400010];
int lendyz,len;
int lenans,ans[200010];
int n,q,h,t,hq,tq,a[200010],belong[200010],hh[200010];
int L[600],R[600];
int sum;
int d[200010];
int Lq[600],Rq[600];
int tt;
vector<int> st[400010];
inline bool cmpx(node1 a,node1 zz){return a.x<zz.x;}
inline void update(int x){
if(x==1){if(d[x+1]==0)sum--;}
else if(x==n){if(d[x-1]==0)sum--;}
else {
if(d[x-1]==0&&d[x+1]==0)sum--;
else if(d[x-1]==1&&d[x+1]==1)sum++;
}
d[x]=0;
}
inline void upt(int k){
tt++;
int x=c[tt].x,y=c[tt].y,z=c[tt].z;
a[x]=y;
if(y<k&&z<k)return ;
if(y>=k&&z>=k)return ;
if(y<k&&z>=k)update(x);
else {
if(x==1){if(d[x+1]==0)sum++;}
else if(x==n){if(d[x-1]==0)sum++;}
else {
if(d[x-1]==0&&d[x+1]==0)sum++;
else if(d[x-1]==1&&d[x+1]==1)sum--;
}
d[x]=1;
}
}
inline void downt(int k){
int x=c[tt].x,y=c[tt].z,z=c[tt].y;
a[x]=y;
if(y<k&&z<k){
tt--;
return ;
}
if(y>=k&&z>=k){
tt--;
return ;
}
if(y<k&&z>=k)update(x);
else {
if(x==1){if(d[x+1]==0)sum++;}
else if(x==n){if(d[x-1]==0)sum++;}
else {
if(d[x-1]==0&&d[x+1]==0)sum++;
else if(d[x-1]==1&&d[x+1]==1)sum--;
}
d[x]=1;
}
tt--;
}
inline bool cmpa(node4 a,node4 zz){
return a.x<zz.x;
}
inline bool cmpb(node4 a,node4 zz){
if(a.id1!=zz.id1)return a.id1<zz.id1;
return a.id2<zz.id2;
}
signed main(){
n=read(),q=read();
for(int i=1;i<=n;i++)a[i]=read(),dyz[++lendyz].x=a[i],dyz[lendyz].id1=1,dyz[lendyz].id2=i;
for(int i=1;i<=q;i++){
qs[i].opt=read(),qs[i].x=read();
dyz[++lendyz].id1=2,dyz[lendyz].id2=i;
if(qs[i].opt==2)qs[i].y=read(),dyz[lendyz].x=qs[i].y;
else dyz[lendyz].x=qs[i].x;
}
sort(dyz+1,dyz+lendyz+1,cmpa);
for(int i=1;i<=lendyz;i++){
if(i==1||dyz[i].x!=dyz[i-1].x)len++;
dyz[i].k=len;
}
sort(dyz+1,dyz+lendyz+1,cmpb);
lendyz=0;
for(int i=1;i<=n;i++)a[i]=dyz[++lendyz].k;
for(int i=1;i<=q;i++){
if(qs[i].opt==1)qs[i].x=dyz[++lendyz].k;
else qs[i].y=dyz[++lendyz].k;
}
hq=650,tq=q/hq;
if(q%hq)tq++;
for(int i=1;i<=n;i++)hh[i]=a[i];
for(int i=1;i<=q;i++){
if(qs[i].opt==2){
qs[i].z=hh[qs[i].x],hh[qs[i].x]=qs[i].y;
}
}
for(int i=1;i<=tq;i++){
Lq[i]=(i-1)*hq+1,Rq[i]=min(i*hq,q);
sum=0;
lenb=0,lenc=0;
for(int i1=Lq[i];i1<=Rq[i];i1++){
if(qs[i1].opt==1){
b[++lenb].x=qs[i1].x,b[lenb].t=lenc,b[lenb].id=++lenans;
}
else {
c[++lenc].x=qs[i1].x,c[lenc].y=qs[i1].y,c[lenc].z=qs[i1].z;
}
}
sort(b+1,b+lenb+1,cmpx);
int u=0,g=b[1].x;
for(int i1=1;i1<=n;i1++){
if(a[i1]>=g){
d[i1]=1;
u++;
}
else {
d[i1]=0;
if(u!=0)sum++;
u=0;
}
st[a[i1]].push_back(i1);
}
if(u!=0)sum++;
int w=b[1].x-1;
tt=0;
for(int i1=1;i1<=lenb;i1++){
while(w<b[i1].x-1){
w++;
for(int i2=0;i2<st[w].size();i2++)update(st[w][i2]);
}
while(tt<b[i1].t)upt(b[i1].x);
ans[b[i1].id]=sum;
while(tt>0)downt(b[i1].x);
}
for(int i1=1;i1<=n;i1++)st[a[i1]].clear();
for(int i1=1;i1<=lenc;i1++)a[c[i1].x]=c[i1].y;
}
for(int i=1;i<=lenans;i++)cout<<ans[i]<<'\n';
return 0;
}::::
其实奶龙ATRI宝宝一开始没想到操作分块，去题解区看复杂度的时候，看到数据结构大神lzyqwq说的：
其实就是第十分块。
才想起来还有这种东西。所以我一开始胡的是一个带
大概就是序列分块，假设取块长为
当然实际取块长肯定不能是