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
| #include"bits/stdc++.h"
#define re register
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
const int maxn=1e5+10,maxm=1e7+10;
int n,m,segcnt,cnt;
int a[maxn],tmp[maxn<<1];
int rt[maxn];
struct tree{
int ls,rs;
int sum,tag;
}tr[maxm];
struct Query{
int op,l,r,c;
}q[maxn];
struct line{
int l,r,c;
inline bool operator < (const line &a)const{
if(r==a.r) return l<a.l;
return r<a.r;
}
};
set<line> s;
inline void up(int p){tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;}
inline void add(int l,int r,int val,int p){
tr[p].tag+=val;
tr[p].sum+=(r-l+1)*val;
}
inline void down(int l,int r,int mid,int p){
if(tr[p].tag){
if(!ls(p)) ls(p)=++segcnt;
if(!rs(p)) rs(p)=++segcnt;
add(l,mid,tr[p].tag,ls(p));
add(mid+1,r,tr[p].tag,rs(p));
tr[p].tag=0;
}
}
inline void update(int l,int r,int L,int R,int val,int &p){
if(!p) p=++segcnt;
if(l>=L&&r<=R){add(l,r,val,p);return;}
int mid=(l+r)>>1;
down(l,r,mid,p);
if(L<=mid) update(l,mid,L,R,val,ls(p));
if(R>mid) update(mid+1,r,L,R,val,rs(p));
up(p);
}
inline int query(int l,int r,int L,int R,int p){
if(!p) return 0;
if(l>=L&&r<=R) return tr[p].sum;
int mid=(l+r)>>1,res=0;
down(l,r,mid,p);
if(L<=mid) res+=query(l,mid,L,R,ls(p));
if(R>mid) res+=query(mid+1,r,L,R,rs(p));
return res;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(re int i=1;i<=n;++i) cin>>a[i],tmp[++cnt]=a[i];
for(re int i=1;i<=m;++i){
cin>>q[i].op>>q[i].l>>q[i].r>>q[i].c;
++q[i].l,++q[i].r;
tmp[++cnt]=q[i].c;
}
sort(tmp+1,tmp+cnt+1);
cnt=unique(tmp+1,tmp+cnt+1)-(tmp+1);
for(re int i=1;i<=n;++i) a[i]=lower_bound(tmp+1,tmp+cnt+1,a[i])-tmp;
for(re int i=1;i<=m;++i) q[i].c=lower_bound(tmp+1,tmp+cnt+1,q[i].c)-tmp;
for(re int i=1;i<=n;++i) update(1,n,i,i,1,rt[a[i]]),s.insert({i,i,a[i]});
for(re int i=1;i<=m;++i){
if(q[i].op==1){
set<line>::iterator it1=s.lower_bound({-1,q[i].l,0}),it2=s.lower_bound({-1,q[i].r,0});
if(it1==it2){
update(1,n,max(q[i].l,it1->l),min(q[i].r,it1->r),-1,rt[it1->c]);
update(1,n,max(q[i].l,it1->l),min(q[i].r,it1->r),1,rt[q[i].c]);
if(it1->l<q[i].l){
line p1={it1->l,q[i].l-1,it1->c};
s.insert(p1);
}
if(it1->r>q[i].r){
line p2={q[i].r+1,it1->r,it1->c};
s.insert(p2);
}
s.erase(it1),s.insert({q[i].l,q[i].r,q[i].c});
continue;
}
++it1;
for(auto it=it1;it!=it2;++it){
update(1,n,it->l,it->r,-1,rt[it->c]);
update(1,n,it->l,it->r,1,rt[q[i].c]);
}
it1=s.erase(it1,it2);
--it1;
if(it1->l<q[i].l){
line p1={it1->l,q[i].l-1,it1->c};
update(1,n,q[i].l,it1->r,-1,rt[it1->c]);
update(1,n,q[i].l,it1->r,1,rt[q[i].c]);
s.erase(it1),s.insert(p1);
}
else{
update(1,n,q[i].l,it1->r,-1,rt[it1->c]);
update(1,n,q[i].l,it1->r,1,rt[q[i].c]);
s.erase(it1);
}
if(it2->r>q[i].r){
line p2={q[i].r+1,it2->r,it2->c};
update(1,n,it2->l,q[i].r,-1,rt[it2->c]);
update(1,n,it2->l,q[i].r,1,rt[q[i].c]);
s.erase(it2),s.insert(p2);
}
else{
update(1,n,it2->l,q[i].r,-1,rt[it2->c]);
update(1,n,it2->l,q[i].r,1,rt[q[i].c]);
s.erase(it2);
}
s.insert({q[i].l,q[i].r,q[i].c});
}
else cout<<query(1,n,q[i].l,q[i].r,rt[q[i].c])<<'\n';
}
return 0;
}
|