1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
| #include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int n,q,a[maxn];
int d[maxn];
#define lowbit(x) ((x)&(-x))
struct node {
int ls,rs,Max,lazy,siz;
}f[10000005];
int cnt=1,root=1,tot;
pair<int,int>o[maxn];
set<int>t[maxn];
int g[maxn];
const int inf=1e9;
void pushup(int rt) {
f[rt].Max=max(f[f[rt].ls].Max,f[f[rt].rs].Max);
}
void pushdown(int rt) {
if (f[rt].lazy) {
int k=f[rt].lazy;f[rt].lazy=0;
f[f[rt].ls].lazy+=k,f[f[rt].rs].lazy+=k;
f[f[rt].ls].Max+=k,f[f[rt].rs].Max+=k;
}
}
void modify(int l,int r,int &rt,int head,int k,int siz) {
if (!rt) rt=++cnt,f[rt].Max=-inf,f[rt].lazy=0,f[rt].siz=0;
f[rt].siz+=siz;
if (l==r) {
f[rt].Max=k;
return ;
}
int mid=l+r>>1;pushdown(rt);
if (head<=mid) modify(l,mid,f[rt].ls,head,k,siz);
else modify(mid+1,r,f[rt].rs,head,k,siz);
pushup(rt);
}
void Update(int l,int r,int &rt,int head,int tail,int k) {
if(head>tail) return ;
if (!rt) rt=++cnt,f[rt].Max=-inf,f[rt].lazy=0,f[rt].siz=0;
if (head<=l&&r<=tail) return f[rt].Max+=k,f[rt].lazy+=k,void();
int mid=l+r>>1;pushdown(rt);
if (head<=mid) Update(l,mid,f[rt].ls,head,tail,k);
if (tail>mid) Update(mid+1,r,f[rt].rs,head,tail,k);
pushup(rt);
}
int Query(int l,int r,int rt,int head,int tail) {
if (!rt) return 0;
if (head<=l&&r<=tail) return f[rt].siz;
int mid=l+r>>1,sum=0;pushdown(rt);
if (head<=mid) sum+=Query(l,mid,f[rt].ls,head,tail);
if (tail>mid) sum+=Query(mid+1,r,f[rt].rs,head,tail);
return sum;
}
int query(int l,int r,int rt,int head,int tail) {
if (!rt) return 0;
if (head<=l&&r<=tail) return f[rt].Max;
int mid=l+r>>1,sum=0;pushdown(rt);
if (head<=mid) sum+=query(l,mid,f[rt].ls,head,tail);
if (tail>mid) sum+=query(mid+1,r,f[rt].rs,head,tail);
return sum;
}
signed main(void){
int i,x,y,j,tmp,ans;
read(n);read(q);
for (i=1;i<=n;i++) read(a[i]);
f[0].Max=-inf;
tot=0;
for (i=1;i<=n;i++) g[++tot]=a[i];
for (i=1;i<=q;i++) {
read(x),read(y),x++,o[i]=mk(x,y);
g[++tot]=y;
}
sort(g+1,g+1+tot);
tot=unique(g+1,g+1+tot)-g-1;
for (i=1;i<=n;i++) {
a[i]=lower_bound(g+1,g+1+tot,a[i])-g;
t[a[i]].insert(i);
modify(1,tot,root,a[i],-inf,1);
}
for (i=1;i<=n;i++) {
modify(1,tot,root,a[i],i-Query(1,tot,1,1,a[i]),0);
}
for (i=1;i<=q;i++) {
x=o[i].fi,y=o[i].se;
y=lower_bound(g+1,g+1+tot,y)-g;
t[a[x]].erase(x);
modify(1,tot,root,a[x],-inf,-1);
if (t[a[x]].begin()!=t[a[x]].end()) {
int tmp=*(--t[a[x]].end());
modify(1,tot,root,a[x],tmp-Query(1,tot,1,1,a[x]),0);
}
Update(1,tot,root,a[x]+1,tot,1);
a[x]=y;
t[a[x]].insert(x);
modify(1,tot,root,a[x],-inf,1);
int tmp=*(--t[a[x]].end()),z=tmp-Query(1,tot,1,1,a[x]);
modify(1,tot,root,a[x],tmp-Query(1,tot,1,1,a[x]),0);
Update(1,tot,root,a[x]+1,tot,-1);
printf("%d\n",max(1,f[1].Max));
}
return 0;
}
|