#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair typedef long long ll; typedef unsigned long long ull; using namespace std; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,q,opt[maxn],all,c0,c1; struct SegTree { struct nd { ll s1,s2; }d[maxn<<2]; #define ls(p) (p<<1) #define rs(p) (p<<1|1) #define s1(p) d[p].s1 #define s2(p) d[p].s2 void modify(int l,int s,int t,int p,int x){ s1(p)+=x,s2(p)+=l*x;if(s==t)return; int mid=s+t>>1; if(l<=mid)modify(l,s,mid,ls(p),x);else modify(l,mid+1,t,rs(p),x); }int calc(int s,int t,int p,int x){ if(s==t){ if(s)return min((ll)x/s,s1(p));return s1(p); }int mid=s+t>>1; if(s2(ls(p))>=x)return calc(s,mid,ls(p),x); return s1(ls(p))+calc(mid+1,t,rs(p),x-s2(ls(p))); } }S00,S11; multiset<int>SS0,SS1; set<int>S; void del_end(int x){ if(opt[x])SS1.erase(SS1.lower_bound(n-x)); else SS0.erase(SS0.lower_bound(n-x)); } void del_begin(int x){ if(opt[x])SS1.erase(SS1.lower_bound(x-1)); else SS0.erase(SS0.lower_bound(x-1)); } void ins_end(int x){ if(opt[x])SS1.insert(n-x); else SS0.insert(n-x); } void ins_begin(int x){ if(opt[x])SS1.insert(x-1); else SS0.insert(x-1); } void INS(int a,int b){ //cout<<"INS "<<a<<" "<<b<<endl; if(opt[a]^opt[b])all++; else if(opt[a])S11.modify(b-a-1,0,n,1,1); else S00.modify(b-a-1,0,n,1,1); } void DEL(int a,int b){ //cout<<"DEL "<<a<<" "<<b<<endl; if(opt[a]^opt[b])all--; else if(opt[a])S11.modify(b-a-1,0,n,1,-1); else S00.modify(b-a-1,0,n,1,-1); } void ins(int x,int c){ if(c)c1--;else c0--; opt[x]=c; auto it=S.upper_bound(x); if(it==S.end()){ if(it!=S.begin())--it,del_end(*it),++it; ins_end(x); }else { int y=(*it); INS(x,y); if(it!=S.begin())--it,DEL((*it),y),++it; }if(it==S.begin()){ if(it!=S.end())del_begin(*it); ins_begin(x); }else { --it;int y=(*it);++it; INS(y,x); }S.insert(x); } void del(int x){ int c=opt[x]; if(c)c1++;else c0++; S.erase(x); auto it=S.upper_bound(x); if(it==S.end()){ if(it!=S.begin())--it,ins_end(*it),++it; del_end(x); }else { int y=(*it); DEL(x,y); if(it!=S.begin())--it,INS((*it),y),++it; } if(it==S.begin()){ if(it!=S.end())ins_begin(*it); del_begin(x); }else { --it;int y=(*it);++it; DEL(y,x); } } int get0(int x){ if(x<0)return 1e9; /*int ct=0; for(int y:S00){ if(x<y)break; ct++,x-=y; }return (S00.size()-ct)*2;*/ int ct=S00.calc(0,n,1,x); int all=S00.s1(1); return (all-ct)*2; } int get1(int x){ if(x<0)return 1e9; /*int ct=0; for(int y:S11){ if(x<y)break; ct++,x-=y; }return (S11.size()-ct)*2;*/ int ct=S11.calc(0,n,1,x); int all=S11.s1(1); return (all-ct)*2; } int calc(){ if(S.empty()){ if((!c0)||(!c1))return 0; return 1; } int res=all;int cnt=0,nw=0,sz=SS0.size(); //cout<<"? "<<SS0.size()<<" "<<SS1.size()<<endl; //cout<<"res : "<<res<<endl; //for(int x:S)cout<<x<<" "<<opt[x]<<endl;cout<<endl; //cout<<"? "<<c0<<" "<<c1<<endl; cnt=get0(c0)+sz; for(int x:SS0)sz--,nw+=x,cnt=min(cnt,get0(c0-nw)+sz); res+=cnt; nw=0,sz=SS1.size(); cnt=get1(c1)+sz; for(int x:SS1)sz--,nw+=x,cnt=min(cnt,get1(c1-nw)+sz); res+=cnt; return res; } void slv(){ n=read(),m=read(),q=read(); up(i,1,n){ int x=read()&1; if(x)c1++;else c0++; } up(i,1,m){ int p=read(),x=read()&1; ins(p,x); } while(q--){ int op=read(),p=read(); if(op==1)del(p); else {if(S.count(p))del(p);int c=read()&1;ins(p,c);} printf("%d\n",calc()); } }int main(){ //freopen("b.in","r",stdin); // freopen("b.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }