题目描述
题解
想不到离线，感觉可以log^2带修主席树维护乱搞
好像线段树维护单调栈有85
离线从后往前做，设当前位置为x，线段树直接维护每个时刻t上[x,n]的后缀最小值以及答案
每个位置的值是若干区间，线段树上区间取min，如果一个点被修改就答案+1
没有区间加吉司机树可以做到严格(O(nlog n))，每次如果往下修改的话会减少至少一段
如果修改最大值就打标记下传，下传时判断是否是同一个值
注意吉司机树维护的是严格次小，要特判全部相同的情况
略微卡常，用freadfwrite不用vector
code
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define inf 2133333333
#define ll long long
//#define file
using namespace std;
struct Vector{
int a[2000001][2],ls[1000001],len;
void push_back(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}
} b1,b2,c;
int tr[4000001][2],Tr[4000001],tag[4000001],ans[1000001],n,m,Q,i,j,k,l,x,y,z,len;
char st[21],st1[27262977],st2[6291457],ch,*Ch=st1;
void Read(int &x) {x=0;while ((*Ch)<'0' || (*Ch)>'9') ++Ch;while ((*Ch)>='0' && (*Ch)<='9') x=x*10+((*Ch)-'0'),++Ch;}
void Write(int x) {int i=0; while (x) st[++i]=(x%10)+'0',x/=10; while (i) st2[++len]=st[i--];st2[++len]='
';}
void Down(int t,int len)
{
if (tag[t]<inf)
{
if (len>1) tag[t*2]=min(tag[t*2],tag[t]),tag[t*2+1]=min(tag[t*2+1],tag[t]);
tr[t][0]=min(tr[t][0],tag[t]),tr[t][1]=min(tr[t][1],tag[t]),tag[t]=inf;
}
}
void down(int t,int len)
{
if (Tr[t] && len>1)
{
if (tr[t*2][0]==tr[t][0]) Tr[t*2]+=Tr[t];
if (tr[t*2+1][0]==tr[t][0]) Tr[t*2+1]+=Tr[t];
Tr[t]=0;
}
}
void up(int t)
{
tr[t][0]=max(tr[t*2][0],tr[t*2+1][0]);
tr[t][1]=0;
if (tr[t*2][0]<tr[t][0]) tr[t][1]=max(tr[t][1],tr[t*2][0]);
if (tr[t*2][1]<tr[t][0]) tr[t][1]=max(tr[t][1],tr[t*2][1]);
if (tr[t*2+1][0]<tr[t][0]) tr[t][1]=max(tr[t][1],tr[t*2+1][0]);
if (tr[t*2+1][1]<tr[t][0]) tr[t][1]=max(tr[t][1],tr[t*2+1][1]);
if (!tr[t][1]) tr[t][1]=tr[t][0];
}
void change(int t,int l,int r,int x,int y,int s)
{
int mid=(l+r)/2;
if (l==r) {down(t,r-l+1);if (tr[t][0]>s) tr[t][0]=tr[t][1]=s,++Tr[t]; return;}
Down(t,r-l+1),Down(t*2,mid-l+1),Down(t*2+1,r-mid),down(t,r-l+1);
if (s>=tr[t][0]) return;
if (x<=l && r<=y && (tr[t][0]==tr[t][1] || s>tr[t][1]))
{
tag[t]=s;Down(t,r-l+1);if (l<r) Down(t*2,mid-l+1),Down(t*2+1,r-mid);
down(t,r-l+1);++Tr[t];
return;
}
if (x<=mid) change(t*2,l,mid,x,y,s);
if (mid<y) change(t*2+1,mid+1,r,x,y,s);
up(t);
}
int find(int t,int l,int r,int x)
{
int mid=(l+r)/2;
if (l==r) return Tr[t];
Down(t,r-l+1),Down(t*2,mid-l+1),Down(t*2+1,r-mid),down(t,r-l+1);
if (x<=mid) return find(t*2,l,mid,x);
else return find(t*2+1,mid+1,r,x);
}
void work()
{
fd(i,n,1)
{
k=m;
for (j=b1.ls[i]; j; j=b1.a[j][1]) {if (b2.a[j][0]<=k) change(1,1,m,b2.a[j][0],k,b1.a[j][0]);k=b2.a[j][0]-1;}
for (j=c.ls[i]; j; j=c.a[j][1]) ans[c.a[j][0]]=find(1,1,m,c.a[j][0]);
}
}
int main()
{
#ifdef file
// freopen("ex_a4.in","r",stdin);
freopen("uoj515.in","r",stdin);
freopen("uoj515.out","w",stdout);
#endif
memset(tr,127,sizeof(tr));
memset(tag,127,sizeof(tag));
fread(st1,1,27262976,stdin);
Read(n),Read(Q);
fo(i,1,n) Read(j),b1.push_back(i,j),b2.push_back(i,1);
m=1;
fo(i,1,Q)
{
Read(x),Read(y);
if (x==1) Read(z),b1.push_back(y,z),b2.push_back(y,m);
else c.push_back(y,m),++m;
}
if (m==1) return 0;--m;
work();
len=-1;
fo(i,1,m) Write(ans[i]);
fwrite(st2,1,len,stdout);
fclose(stdin);
fclose(stdout);
return 0;
}