树状数组
树状数组1
题意：单点修改，求前缀和
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
ll a[N],c[N];
int n;
inline int lowbit(int x) {return x&-x;}
inline void update(int x,ll a) {while(x<=n) c[x]+=a,x+=lowbit(x);}
inline ll query(int x) {ll res = 0;while(x) res+=c[x],x-=lowbit(x);return res;}
void solve()
{
int q;
cin>>n>>q;
for(int i=1;i<=n;++i)
{
cin>>a[i];
update(i,a[i]);
}
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int x,d;
//将a[x]修改为d等价于a[x]+=d-a[x]
cin>>x>>d;
update(x,d-a[x]);
a[x] = d;
}
else
{
int x;
cin>>x;
cout<<query(x)<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
树状数组2（bushi）
题意：区间改，区间查
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
//用l,r表示在线段树在区间[1,n]上对应的左右端点
//用p<<1,p<<1|1表示线段树的左右儿子
//用x,y表示查询或修改的区间
int a[N];
int n,q;
struct node
{
int l,r;
ll sum,lazy;
}tr[N<<2];
void pushup(int p)
{
tr[p].sum = tr[p<<1].sum+tr[p<<1|1].sum;
}
void pushdown(int p)
{
if(!tr[p].lazy) return ;
int l = tr[p].l, r = tr[p].r, m = l+(r-l)/2;
ll lazy = tr[p].lazy;
tr[p<<1].sum += lazy*(m-l+1);
tr[p<<1|1].sum += lazy*(r-m);
tr[p<<1].lazy += lazy;
tr[p<<1|1].lazy +=lazy;
tr[p].lazy = 0;
}
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].sum = a[l];
return ;
}
int m = l+(r-l)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
//注意此处d用ll,线段树与值有关统一用ll
void update(int x,int y,int p,ll d)
{
int l = tr[p].l, r = tr[p].r;
if(x<=l&&r<=y)
{
tr[p].sum += d*(r-l+1);
tr[p].lazy+=d;
return ;
}
pushdown(p);
int m = l+(r-l)/2;
if(x<=m) update(x,y,p<<1,d);
if(y>m) update(x,y,p<<1|1,d);
pushup(p);
}
ll query(int x,int y,int p)
{
int l = tr[p].l, r = tr[p].r;
if(x>r||l>y) return 0;
if(x<=l&&r<=y) return tr[p].sum;
pushdown(p);
return query(x,y,p<<1)+query(x,y,p<<1|1);
}
void solve()
{
cin>>n>>q;
build(1,n,1);
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int l,r,d;
cin>>l>>r>>d;
update(l,r,1,d);
}
else
{
int x;
cin>>x;
cout<<query(1,x,1)<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
逆序对
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 100010;
int c[N];
int n;
inline int lowbit(int x) {return x&-x;}
inline void update(int x,int d) {while(x<=n) c[x]+=d,x+=lowbit(x);}
inline ll sum(int x) {ll res = 0;while(x) res+=c[x],x-=lowbit(x);return res;}
void solve()
{
cin>>n;
ll ans = 0;
for(int i=1;i<=n;++i)
{
int x;
cin>>x;
update(x,1);
ans+=sum(n)-sum(x);
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
树状数组二分
题意：1.修改a[x] = d,2.输入s,求最大的T,使得\(\sum_{i=1}^{T}a_i\)<=s
解析：从高位向低位枚举,根据树状数组定义f(i) = \(\sum_{i=i-lowbit(i)+1}^{i}a_i\) 类似倍增当pos'变成pos时，t增加了c[pos'+1]~c[pos],最终确定位置T
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
ll a[N],c[N];
int n,q;
inline int lowbit(int x) {return x&-x;}
inline void update(int x,int d) {while(x<=n) c[x]+=d,x+=lowbit(x);}
inline int log_2(ll x) {return 63-__builtin_clzll(x);}
inline int query(ll s)
{
int x = log_2(n)+1; //此处的x应该为log2(n)的上取整
ll t = 0, pos = 0;
for(int j=x;j>=0;--j)
{
if(pos+(1<<j)<=n&&t+c[pos+(1<<j)]<=s)
{
t+=c[pos+(1<<j)];
//注意应该先更新t后更新pos
pos+=(1<<j);
}
}
return pos;
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i)
{
cin>>a[i];
update(i,a[i]);
}
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int x,d;
cin>>x>>d;
update(x,d-a[x]);//将修改变为增加
a[x] = d;
}
else
{
ll s;
cin>>s;
cout<<query(s)<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
二维数组数组
题意：1.修改a[x][y] = d 2.查询\(\sum_{i=1}^{x}\sum_{j=1}^{y}a_{i,j}\)
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 501;
ll a[N][N],c[N][N];
int n,m,q;
inline int lowbit(int x) {return x&-x;}
inline void update(int x,int y,int d)
{
for(int p=x;p<=n;p+=lowbit(p))
for(int q=y;q<=m;q+=lowbit(q))
c[p][q]+=d;
}
inline ll query(int x,int y)
{
//注意此处不能直接用x,y来减
ll res = 0;
for(int p=x;p;p-=lowbit(p))
for(int q=y;q;q-=lowbit(q))
res+=c[p][q];
return res;
}
void solve()
{
cin>>n>>m>>q;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
cin>>a[i][j];
update(i,j,a[i][j]);
}
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int x,y,d;
cin>>x>>y>>d;
update(x,y,d-a[x][y]);//将修改变为增加
a[x][y] = d;
}
else
{
int x,y;
cin>>x>>y;
cout<<query(x,y)<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
线段树
线段树1
题意：1.修改a[x] = d。2.查询l~r的最小值及其出现次数
给出封装化线段树
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int n,q;
int a[N];
struct info
{
int minn,mincnt;
};
info operator + (const info& l,const info& r)
{
info a;
a.minn = min(l.minn,r.minn);
if(l.minn==r.minn) a.mincnt = l.mincnt+r.mincnt;
else if(l.minn<r.minn) a.mincnt = l.mincnt;
else a.mincnt = r.mincnt;
return a;
}
struct node
{
int l,r;
info val;
}tr[N<<2];
void pushup(int p)
{
tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].val = {a[l],1};
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
void update(int x,int d,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==r)
{
tr[p].val = {d,1};
return ;
}
int m = (l+r)/2;
if(x<=m) update(x,d,p<<1);
else update(x,d,p<<1|1);
pushup(p);
}
info query(int x,int y,int p)
{
int l = tr[p].l,r = tr[p].r;
if(x==l&&r==y) return tr[p].val;
info ans;
int m = (l+r)/2;
if(y<=m) return query(x,y,p<<1);
else if(x>m) return query(x,y,p<<1|1);
else return query(x,m,p<<1)+query(m+1,y,p<<1|1);
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
//cout<<query(1,n,1).minn<<' '<<query(1,n,1).mincnt<<'\n';
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int x,d;
cin>>x>>d;
update(x,d,1);
}
else
{
int x,y;
cin>>x>>y;
auto res = query(x,y,1);
cout<<res.minn<<" "<<res.mincnt<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
线段树2
题意：1.修改a[x] = d 2.查询[l,r]的最大子段和
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int n,q;
int a[N];
struct info
{
ll mms,mpre,msuf,sum;
info() {}
info(int a) :mms(a),mpre(a),msuf(a),sum(a) {}
};
info operator + (const info& l,const info& r)
{
info a;
a.mms = max({l.mms,r.mms,l.msuf+r.mpre});
a.mpre = max(l.mpre,l.sum+r.mpre);
a.msuf = max(r.msuf,l.msuf+r.sum);
a.sum = l.sum + r.sum;
return a;
}
struct node
{
int l,r;
info val;
}tr[N<<2];
void pushup(int p)
{
tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].val = info(a[l]);
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
//单点修改
void update(int x,int d,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==r)
{
tr[p].val = info(d);
return ;
}
int m = (l+r)/2;
if(x<=m) update(x,d,p<<1);
else update(x,d,p<<1|1);
pushup(p);
}
info query(int x,int y,int p)
{
int l = tr[p].l,r = tr[p].r;
if(x==l&&r==y) return tr[p].val;
info ans;
int m = (l+r)/2;
if(y<=m) return query(x,y,p<<1);
else if(x>m) return query(x,y,p<<1|1);
else return query(x,m,p<<1)+query(m+1,y,p<<1|1);
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
//cout<<query(1,n,1).minn<<' '<<query(1,n,1).mincnt<<'\n';
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int x,d;
cin>>x>>d;
update(x,d,1);
}
else
{
int x,y;
cin>>x>>y;
auto res = query(x,y,1);
cout<<res.mms<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
线段树打标记1
题意：1.将[l,r]加上d 2.求[l,r]的max
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int n,q;
int a[N];
struct info
{
ll maxn;
info() {}
info(int a) :maxn(a) {}
};
struct tag
{
ll add;
};
//用于合并左右子树
info operator + (const info& l,const info& r)
{
info a;
a.maxn = max(l.maxn , r.maxn);
return a;
}
//settag时需要处理val和tag的关系
info operator + (const info &v,const tag& t)
{
info a;
a.maxn = v.maxn + t.add;
return a;
}
//下推标记时标记的合并
tag operator + (const tag &t1,const tag&t2)
{
tag t;
t.add = t1.add + t2.add;
return t;
}
struct node
{
int l,r;
info val;
tag t;
}tr[N<<2];
void settag(int p,tag t)
{
tr[p].val = tr[p].val + t;
tr[p].t = tr[p].t + t;
}
void pushup(int p)
{
tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
void pushdown(int p)
{
if(tr[p].t.add!=0) //标记非空
{
settag(p<<1,tr[p].t);
settag(p<<1|1,tr[p].t);
tr[p].t.add = 0; //下推完记得清空
}
}
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].val = info(a[l]);
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
//区间修改
void update(int x,int y,tag C,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==x&&r==y)
{
settag(p,C);
return ;
}
pushdown(p);
int m = (l+r)/2;
if(y<=m) update(x,y,C,p<<1);
else if(x>m) update(x,y,C,p<<1|1);
else
{
update(x,m,C,p<<1);
update(m+1,y,C,p<<1|1);
}
pushup(p);
}
info query(int x,int y,int p)
{
int l = tr[p].l,r = tr[p].r;
if(x==l&&r==y) return tr[p].val;
pushdown(p);
info ans;
int m = (l+r)/2;
if(y<=m) return query(x,y,p<<1);
else if(x>m) return query(x,y,p<<1|1);
else return query(x,m,p<<1)+query(m+1,y,p<<1|1);
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
//cout<<query(1,n,1).minn<<' '<<query(1,n,1).mincnt<<'\n';
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int x,y,C;
cin>>x>>y>>C;
update(x,y,(tag){C},1);
}
else
{
int x,y;
cin>>x>>y;
auto res = query(x,y,1);
cout<<res.maxn<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
线段树打标记2
题意：1.[l,r]加d 2.[l,r]乘d 3.[l,r]等于d 4.查询[l,r]
非结构化写法
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int n,q;
int a[N];
const int mod = 1e9+7;
//一般要修改tag的构造函数
struct tag
{
ll mul,add;
tag():mul(1),add(0) {}
tag(ll a,ll b):mul(a),add(b) {}
};
//下推标记时标记的合并,一定要注意
tag operator + (const tag &t1,const tag&t2)
{
tag t;
t.mul = t1.mul*t2.mul%mod;
t.add = (t1.mul*t2.add%mod + t1.add)%mod;
return t;
}
//非封装化写法(当info内需要保留的内容少时)
struct node
{
int l,r;
ll sum,sz;
tag t;
}tr[N<<2];
//settag里包裹tag对当前节点的影响(需要修改)和tag的下推(无需修改)
void settag(int p,tag t)
{
//注意此处的顺序要用新的tag更新原本的tag
tr[p].sum = (t.mul*tr[p].sum%mod + t.add*tr[p].sz%mod)%mod;
tr[p].t = t + tr[p].t;
}
//注意合并写法
void pushup(int p)
{
tr[p].sum = (tr[p<<1].sum + tr[p<<1|1].sum)%mod;
}
//注意修改标记
void pushdown(int p)
{
if(tr[p].t.mul!=1||tr[p].t.add!=0) //标记非空
{
settag(p<<1,tr[p].t);
settag(p<<1|1,tr[p].t);
tr[p].t.mul = 1;
tr[p].t.add = 0; //下推完记得清空
}
}
//一般不用修改
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r,tr[p].sz = r-l+1;
if(l==r)
{
tr[p].sum = a[l];
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
//一般不用修改
void update(int x,int y,tag C,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==x&&r==y)
{
settag(p,C);
return ;
}
pushdown(p);
int m = (l+r)/2;
if(y<=m) update(x,y,C,p<<1);
else if(x>m) update(x,y,C,p<<1|1);
else
{
update(x,m,C,p<<1);
update(m+1,y,C,p<<1|1);
}
pushup(p);
}
//一般不用修改
ll query(int x,int y,int p)
{
int l = tr[p].l,r = tr[p].r;
if(x==l&&r==y) return tr[p].sum;
pushdown(p);
int m = (l+r)/2;
if(y<=m) return query(x,y,p<<1);
else if(x>m) return query(x,y,p<<1|1);
else return (query(x,m,p<<1)+query(m+1,y,p<<1|1))%mod;
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op==1)
{
int x,y,d;
cin>>x>>y>>d;
update(x,y,tag(1,d),1);
}
else if(op==2)
{
int x,y,d;
cin>>x>>y>>d;
update(x,y,tag(d,0),1);
}
else if(op==3)
{
int x,y,d;
cin>>x>>y>>d;
update(x,y,tag(0,d),1);
}
else
{
int x,y;
cin>>x>>y;
ll res = query(x,y,1);
cout<<res<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
结构化写法
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int n,q;
int a[N];
const int mod = 1e9+7;
//一般要修改info和tag的构造函数
struct info
{
ll sum,sz;
info() {}
info(ll a) :sum(a),sz(1) {}
};
struct tag
{
ll mul,add;
tag():mul(1),add(0) {}
tag(ll a,ll b):mul(a),add(b) {}
};
//线段树如果wa掉一定先检查这三个重载
//用于合并左右子树
info operator + (const info& l,const info& r)
{
info a;
a.sum = (l.sum+r.sum)%mod;
a.sz = l.sz+r.sz;
return a;
}
//settag时需要处理val和tag的关系
//本题中由于更新sum需要区间长度，故info中添加了sz
//注意此处由于是返回一个info,同时要保留sz信息
info operator + (const info &v,const tag& t)
{
info a;
a.sum = (v.sum*t.mul%mod + t.add*v.sz%mod)%mod;
a.sz = v.sz;
return a;
}
//下推标记时标记的合并
tag operator + (const tag &t1,const tag&t2)
{
tag t;
t.mul = t1.mul*t2.mul%mod;
t.add = (t1.mul*t2.add%mod + t1.add)%mod;
return t;
}
struct node
{
int l,r;
info val;
tag t;
}tr[N<<2];
//一般不用修改，但要注意tag更新顺序
void settag(int p,tag t)
{
tr[p].val = tr[p].val + t;
//注意此处的顺序要用新的tag更新原本的tag
tr[p].t = t + tr[p].t;
}
//一般不用修改
void pushup(int p)
{
tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
//一般需要修改标记非空的判定条件
void pushdown(int p)
{
if(tr[p].t.add!=0||tr[p].t.mul!=1) //标记非空
{
settag(p<<1,tr[p].t);
settag(p<<1|1,tr[p].t);
tr[p].t.add = 0; //下推完记得清空
tr[p].t.mul = 1;
}
}
//一般不用修改
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].val = info(a[l]);
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
//一般不用修改
void update(int x,int y,tag C,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==x&&r==y)
{
settag(p,C);
return ;
}
pushdown(p);
int m = (l+r)/2;
if(y<=m) update(x,y,C,p<<1);
else if(x>m) update(x,y,C,p<<1|1);
else
{
update(x,m,C,p<<1);
update(m+1,y,C,p<<1|1);
}
pushup(p);
}
//一般不用修改
info query(int x,int y,int p)
{
int l = tr[p].l,r = tr[p].r;
if(x==l&&r==y) return tr[p].val;
pushdown(p);
info ans;
int m = (l+r)/2;
if(y<=m) return query(x,y,p<<1);
else if(x>m) return query(x,y,p<<1|1);
else return query(x,m,p<<1)+query(m+1,y,p<<1|1);
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op==1)
{
int x,y,d;
cin>>x>>y>>d;
update(x,y,tag(1,d),1);
}
else if(op==2)
{
int x,y,d;
cin>>x>>y>>d;
update(x,y,tag(d,0),1);
}
else if(op==3)
{
int x,y,d;
cin>>x>>y>>d;
update(x,y,tag(0,d),1);
}
else
{
int x,y;
cin>>x>>y;
auto res = query(x,y,1);
cout<<res.sum<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
线段树上二分
题意:1.a[x] = d 2.求[l,r]第一个>=d的下标
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int n,q;
int a[N];
struct info
{
int maxn;
};
info operator + (const info& l,const info& r)
{
info a;
a.maxn = max(l.maxn,r.maxn);
return a;
}
struct node
{
int l,r;
info val;
}tr[N<<2];
void pushup(int p)
{
tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].val = {a[l]};
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
void update(int x,int d,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==r)
{
tr[p].val = {d};
return ;
}
int m = (l+r)/2;
if(x<=m) update(x,d,p<<1);
else update(x,d,p<<1|1);
pushup(p);
}
int search(int x,int y,int d,int p)
{
int l = tr[p].l,r = tr[p].r;
int m = (l+r)/2;
if(l==x&&y==r)
{
if(tr[p].val.maxn < d) return -1;
if(l==r) return l;
if(tr[p<<1].val.maxn>=d) return search(x,m,d,p<<1);
else return search(m+1,y,d,p<<1|1);
}
if(y<=m) return search(x,y,d,p<<1);
else if(x>m) return search(x,y,d,p<<1|1);
else
{
int tmp = search(x,m,d,p<<1);
if(tmp!=-1) return tmp;
else return search(m+1,y,d,p<<1|1);
}
}
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i) cin>>a[i];
build(1,n,1);
for(int i=1;i<=q;++i)
{
int op;
cin>>op;
if(op&1)
{
int x,d;
cin>>x>>d;
update(x,d,1);
}
else
{
int x,y,d;
cin>>x>>y>>d;
int res = search(x,y,d,1);
cout<<res<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
扫描线
二维数点
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
//以y轴扫描，y为第一关键字，操作为第二关键字
vector<array<int,4>> event;
vector<int> vx;// 用于离散化
const int N = 2e5+10;
int m;
int c[N*2],ans[N];
inline int lowbit(int x) {return x&-x;}
inline void update(int x,int y) {while(x<=m) c[x]+=y,x+=lowbit(x);}
inline ll sum(int x) {ll res=0;while(x) res+=c[x],x-=lowbit(x);return res;}
int mp(int x)
{
//注意可能查询时存在x不在vx里的，若用lower_bound可能会有下标冲突
return upper_bound(vx.begin(),vx.end(),x) - vx.begin() ;
};
void solve()
{
int n,q;
cin>>n>>q;
for(int i=0;i<n;++i)
{
int x,y;
cin>>x>>y;
vx.push_back(x);
event.push_back({y,0,x});
}
//二维数点 +x2y2 + x1-1,y1-1,-x1-1,y2,-x2,y1-1
for(int i=1;i<=q;++i)
{
int x1,x2,y1,y2;
cin>>x1>>x2>>y1>>y2;
//需要保存标号
//2为加，1为减
event.push_back({y2,2,x2,i});
event.push_back({y1-1,2,x1-1,i});
event.push_back({y2,1,x1-1,i});
event.push_back({y1-1,1,x2,i});
}
sort(event.begin(),event.end());
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
m = vx.size();
for(auto evt:event)
{
int pos = mp(evt[2]);
if(!evt[1]) {update(pos,1);}
else
{
//对于一个event来说,sum(pos)相当于存了一个(evt[0],pos)的矩阵
int tmp = sum(pos);
if(evt[1]==1) ans[evt[3]]-=tmp;
else ans[evt[3]]+=tmp;
}
}
for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
区间不同数之和
思路一：转化为二维数点，pre[i]表示i上一次出现的位置，查找的点为L<= i <= R, pre[i] < L 的点值和
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
//以y轴扫描，y为第一关键字，操作为第二关键字
vector<array<int,4>> event;
vector<int> vx;// 用于离散化
const int N = 2e5+10;
int m;
ll c[N*2],ans[N];
inline int lowbit(int x) {return x&-x;}
inline void update(int x,int y) {while(x<=m) c[x]+=y,x+=lowbit(x);}
inline ll sum(int x) {ll res=0;while(x) res+=c[x],x-=lowbit(x);return res;}
int last[N],pre[N];
//转化到二维数点，求i在[l,r],pre[i]<l的点的个数
void solve()
{
int n,q;
cin>>n>>q;
memset(last,-1,sizeof last);
for(int i=1;i<=n;++i)
{
int a;
cin>>a;
pre[i] = last[a];
last[a] = i;
//x为下标，y为pre[i],此时evt[3]里存的是数值
event.push_back({pre[i],0,i,a});
}
//二维数点 +x2y2 + x1-1,y1-1,-x1-1,y2,-x2,y1-1
for(int i=1;i<=q;++i)
{
int l,r;
cin>>l>>r;
//需要保存标号
//2为加，1为减
event.push_back({l-1,2,r,i});
event.push_back({l-1,1,l-1,i});
}
sort(event.begin(),event.end());
m = n;
for(auto evt:event)
{
int pos = evt[2];
//此时更新应该+a
if(!evt[1]) update(pos,evt[3]);
else
{
//对于一个event来说,sum(pos)相当于存了一个(evt[0],pos)的矩阵
ll tmp = sum(pos);
if(evt[1]==1) ans[evt[3]]-=tmp;
else ans[evt[3]]+=tmp;
}
}
for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
思路二 ： 枚举r，维护ans[l]表示[l,r]的答案，当r从r-1转移到r时，只有pos[r]<i 的区间需要增加
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int m;
//注意由于扫描时可能树状数组的区间和题目中的n不一样，需要考虑后赋值
ll c[N*2],ans[N];
inline int lowbit(int x) {return x&-x;}
inline void update(int x,int y) {while(x<=m) c[x]+=y,x+=lowbit(x);}
inline ll sum(int x) {ll res=0;while(x) res+=c[x],x-=lowbit(x);return res;}
//pre[r]表示上次一a[r]出现的位置
int last[N],pre[N],a[N];
vector<PII> qu[N];
void solve()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;++i)
{
cin>>a[i];
pre[i] = last[a[i]];
last[a[i]] = i;
}
for(int i=1;i<=q;++i)
{
int l,r;
cin>>l>>r;
qu[r].push_back({l,i});
}
//以r从1~n,对每一个r，ans[i]表示i~r的答案
//可以发现当r从r-1向r更新时,只有pos[r]<i的区间会被更新
m = n;
for(int r=1;r<=n;++r)
{
int p = pre[r];
update(p+1,a[r]);
update(r+1,-a[r]);
for(auto t:qu[r])
{
ans[t.y] = sum(t.x);
}
}
for(int i=1;i<=q;++i) cout<<ans[i]<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
矩形面积并
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
//以y轴扫描，y为第一关键字，操作为第二关键字
vector<array<int,4>> event;
const int N = 2e5+10;
vector<int> vx;
//由于左右端点线段树需要开八倍
struct info
{
int minn,mincnt;
info() {}
info(int a,int x) :minn(a), mincnt(x) {}
};
struct tag
{
ll add;
};
info operator + (const info& l,const info& r)
{
info a;
a.minn = min(l.minn,r.minn);
if(l.minn==r.minn) a.mincnt = l.mincnt+r.mincnt;
else if(l.minn<r.minn) a.mincnt = l.mincnt;
else a.mincnt = r.mincnt;
return a;
}
info operator + (const info &v,const tag& t)
{
info a = v;
a.minn = v.minn + t.add;
return a;
}
//下推标记时标记的合并
tag operator + (const tag &t1,const tag&t2)
{
tag t;
t.add = t1.add + t2.add;
return t;
}
struct node
{
int l,r;
info val;
tag t;
}tr[N<<4];
void settag(int p,tag t)
{
tr[p].val = tr[p].val + t;
tr[p].t = tr[p].t + t;
}
void pushup(int p)
{
tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
void pushdown(int p)
{
if(tr[p].t.add!=0) //标记非空
{
settag(p<<1,tr[p].t);
settag(p<<1|1,tr[p].t);
tr[p].t.add = 0; //下推完记得清空
}
}
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].val = info(0,vx[l]-vx[l-1]);
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
//区间修改
void update(int x,int y,tag C,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==x&&r==y)
{
settag(p,C);
return ;
}
pushdown(p);
int m = (l+r)/2;
if(y<=m) update(x,y,C,p<<1);
else if(x>m) update(x,y,C,p<<1|1);
else
{
update(x,m,C,p<<1);
update(m+1,y,C,p<<1|1);
}
pushup(p);
}
int m;
//vector<int> vx;
void divide()
{
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
}
int mp(int x)
{
return upper_bound(vx.begin(),vx.end(),x)-vx.begin();
}
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
{
int x1,x2,y1,y2;
cin>>x1>>x2>>y1>>y2;
vx.push_back(x1);
vx.push_back(x2);
event.push_back({y1,1,x1,x2});
event.push_back({y2,-1,x1,x2});
}
divide();
//化点为段，数量减一
m = vx.size()-1;
build(1,m,1);
//注意扫描之前必须先排序
sort(event.begin(),event.end());
int totlen = tr[1].val.mincnt;
ll ans = 0;
int prey = 0;
for(auto evt:event)
{
int cov = totlen;
//由于给的是点坐标而有效面积是区间所以x2需要减一
int x1 = mp(evt[2]),x2 = mp(evt[3])-1;
//注意若线段树的左区间大于右区间会RE
if(x1>x2) continue;
if(!tr[1].val.minn)
{
cov -= tr[1].val.mincnt;
}
//先统计后修改
ans += (ll)cov*(evt[0]-prey);
//注意prey的更新
prey = evt[0];
update(x1,x2,(tag){evt[1]},1);
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
权值线段树（特值bit建树）
异或第k小
题意 ：给定n个数，q次询问，每次给x,k，查询a[i]^x的第k小
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10,M = 31;
struct node
{
int s[2];
int sz;
}tr[N*32];
void solve()
{
int root = 0,tot = 0;
root = ++tot;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
int x;
cin>>x;
int p = root;
for(int j=M;j>=0;--j)
{
tr[p].sz++;
int w = (x>>j)&1;
if(!tr[p].s[w]) tr[p].s[w] = ++tot;
p = tr[p].s[w];
}
tr[p].sz++;
}
for(int i=0;i<m;++i)
{
int x,k;
cin>>x>>k;
int p = root;
int ans = 0;
for(int j=M;j>=0;--j)
{
int w = (x>>j)&1;
//和x当前位一样的数大于等于k，ans当前位为0
//注意查找当前的sz需要再套一个tr
if(tr[tr[p].s[w]].sz>=k)
{
p = tr[p].s[w];
}
else
{
k -= tr[tr[p].s[w]].sz;
ans ^= (1<<j);
p = tr[p].s[w^1];
}
}
cout<<ans<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
mex
求[l,r]的mex值
枚举r，更新pos[a[r]]，线段树上二分寻找下标最小的x使得pos[x]<l
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
int n,q;
int a[N];
struct info
{
int minn;
};
info operator + (const info& l,const info& r)
{
info a;
a.minn = min(l.minn,r.minn);
return a;
}
struct node
{
int l,r;
info val;
}tr[N<<2];
void pushup(int p)
{
tr[p].val = tr[p<<1].val + tr[p<<1|1].val;
}
void build(int l,int r,int p)
{
tr[p].l = l,tr[p].r = r;
if(l==r)
{
tr[p].val = {0};
return ;
}
int m = (l+r)/2;
build(l,m,p<<1);
build(m+1,r,p<<1|1);
pushup(p);
}
void update(int x,int d,int p)
{
int l = tr[p].l, r = tr[p].r;
if(l==r)
{
tr[p].val = {d};
return ;
}
int m = (l+r)/2;
if(x<=m) update(x,d,p<<1);
else update(x,d,p<<1|1);
pushup(p);
}
int search(int x,int y,int d,int p)
{
int l = tr[p].l , r = tr[p].r;
int m = (l+r)/2;
if(tr[p].val.minn > d) return -1;
if(l==r) return l;
if(tr[p<<1].val.minn < d) return search(x,m,d,p<<1);
else return search(m+1,y,d,p<<1|1);
}
vector<PII> qu[N];
int ans[N],pos[N];
void solve()
{
cin>>n>>q;
for(int i=1;i<=n;++i)
{
cin>>a[i];
a[i] = min(a[i],n+1);
}
build(1,n,1);
for(int i=1;i<=q;++i)
{
int l,r;
cin>>l>>r;
qu[r].push_back({l,i});
}
for(int r=1;r<=n;++r)
{
//更新a[r]+1处的值为r(将0转化到1)
update(a[r]+1,r,1);
//查找最小的x使得pos[x]<l
for(auto [l,i]:qu[r]) ans[i] = search(1,n,l,1);
}
for(int i=1;i<=q;++i) cout<<ans[i]-1<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
笛卡尔树
题意:给定一个 1∼n的排列p，构造一个 1∼n的排列 q，满足对于任意区间 l,r，满足 pl,pl+1,…,pr中的最小值的位置，和ql,ql+1,…,qr的最小值的位置相同。输出满足条件的字典序最小的 q
题解：所有区间的最小值位置一样即两个排列的笛卡尔树一样，由于要字典序最小，所以再p的笛卡尔树上先序遍历赋值构造即可
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 1e6+10;
int a[N],l[N],r[N],ans[N];
int tot,n;
void dfs(int u)
{
ans[u] = ++tot;
if(l[u]) dfs(l[u]);
if(r[u]) dfs(r[u]);
}
void build()
{
int root = 0;
stack<int> stk;
for(int i=1;i<=n;++i)
{
int last = 0;
while(stk.size()&&a[i]<a[stk.top()])
{
last = stk.top();
stk.pop();
}
if(!stk.empty()) r[stk.top()] = i;
else root = i;
l[i] = last;
stk.push(i);
}
//root保存了根节点的编号
dfs(root);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
build();
for(int i=1;i<=n;++i) cout<<ans[i]<<" \n"[i==n];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
st表
RMQ
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
unsigned int A, B, C;
inline unsigned int rng61() {
A ^= A << 16;
A ^= A >> 5;
A ^= A << 1;
unsigned int t = A;
A = B;
B = C;
C ^= t ^ A;
return C;
}
const int N = 1e6+10;
int n,q;
uint a[N],st[22][N];
void init_st()
{
for(int i=1;i<=n;++i) st[0][i] = a[i];
//注意先枚举的是j
for(int j=1;j<=20;++j)
for(int i=1;i+(1<<(j-1))-1<=n;++i)
{
st[j][i] = max(st[j-1][i] , st[j-1][i+(1<<(j-1))]);
}
}
uint RMQ(int l,int r)
{
//使用库函数__lg会比数组更快
int len = __lg(r-l+1);
return max(st[len][l],st[len][r-(1<<len)+1]);
}
void solve()
{
cin>>n>>q>>A>>B>>C;
uint ans = 0;
for (int i = 1; i <= n; i++) {
a[i] = rng61();
}
init_st();
for (int i = 1; i <= q; i++) {
unsigned int l = rng61() % n + 1, r = rng61() % n + 1;
if (l > r) swap(l, r);
int tmp = RMQ(l,r);
ans^=tmp;
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
带权并查集
题意：n个数 操作1: 给定线索$ a[l] - a[r] = x $ 2: 回答a[l]-a[r],题目通过2的答案修改t，强制在线
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
ll w[N];//用w[i]表示a[i]-a[p];
int f[N];
int find(int x)
{
if(f[x]==x) return x;
int p = f[x];
int q = find(f[x]);
//路径压缩的时候维护w[i]
//w[x] = a[x] - a[p];
//w[p] = a[p] - a[rt]
w[x] = w[x] + w[p];
//注意路径压缩的返回值需要修改f[x]
return f[x] = q;
}
void solve()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;++i) f[i] = i;
ll t = 0;
for(int i=0;i<q;++i)
{
int op;
cin>>op;
ll l,r,x;
if(op&1)
{
cin>>l>>r>>x;
//线索a[l]-a[r] = x;
l = (l+t)%n+1, r = (r+t)%n+1;
int pl = find(l), pr = find(r);
if(pl == pr) continue;//如果之前就在一个并查集无需操作
f[pl] = pr; //将l所在并查集合并到r
// w[pl] = a[pl] - a[pr]
// w[l] = a[l] - a[pl]
// w[r] = a[r] - a[pr]
//合并时要用w[l],w[r]维护w[pl]
// w[l] - w[r] = a[l] - a[r] -w[pl] = x - w[pl]
// w[pl] = x + w[r] - w[l]
w[pl] = x + w[r] - w[l];
}
else
{
cin>>l>>r;
l = (l+t)%n+1, r = (r+t)%n+1;
int pl = find(l), pr = find(r);
if(pl != pr) continue;
ll res = w[l] - w[r];
cout<<res<<'\n';
t = abs(res);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
根号分治
经典分治（取模数，普通图）
等差数列加
题意：初始值为0长度为n的数组a 操作1.令a[i%x==y] += d 2.求a[x]
题解: 对于 \(d>\sqrt{n}\) 直接操作不会超过\(\sqrt{n}\)次，对 \(d<\sqrt{n}\) 的数用\(f[i][j]\)保存mod i == j的加和
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int B = 500;
//f[i][j]表示的是%i后下标为j的数要增加的数
ll f[B+1][B];
void solve()
{
int B = 500;
int n,q;
cin>>n>>q;
vector<ll> a(n+1);
while(q--)
{
int op;
cin>>op;
//cout<<op<<'\n';
if(op&1)
{
int x,y,d;
cin>>x>>y>>d;
if(x<=B) f[x][y] += d;
else
{
for(int i=y;i<=n;i+=x) a[i] += d;
}
}
else
{
int x;
cin>>x;
ll tmp = 0;//注意此处不能修改a[x]的值
for(int i=1;i<=B;++i) tmp += f[i][x%i];
cout<<a[x] + tmp<<'\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
图染色
题意：n个点，m条边的无向图，初始全为白点 操作1.翻转x 2.查询x的邻居有多少黑点
题解：对度数小的点查询直接遍历，对度数大的点在修改时维护出来，给每个点建大点图，每个点至多会有\(\sqrt{n}\)条边
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 2e5+10;
const int B = 500;
bool st[N],big[N];
vector<int> e[N],bige[N];
int ans[N];
void solve()
{
int n,m,q;
cin>>n>>m>>q;
while(m--)
{
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;++i)
{
//判断一个点是不是大点
big[i] = (e[i].size()>=B);
}
for(int i=1;i<=n;++i)
{
//建每个点的大点图来维护大点的邻居
for(auto v:e[i]) if(big[v]) bige[i].push_back(v);
}
while(q--)
{
int op,x;
cin>>op>>x;
if(op&1)
{
//对于每次翻转都维护其大点图
st[x] = !st[x];
for(auto v:bige[x])
{
if(st[x]) ans[v]++;
else ans[v]--;
}
}
else
{
//对于大点的答案直接输出
if(big[x]) cout<<ans[x]<<'\n';
else
{
//对于小点的查询直接遍历即可
int tmp = 0;
for(auto v:e[x]) if(st[v]) tmp++;
cout<<tmp<<'\n';
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
}
莫队、
莫队是解决容易完成区间添加和删除单个元素，但难以合并的问题，将区间合并的问题转化为元素的增加和减少
小z的袜子
题意：c[i]表示袜子的种类 每个询问求每次求区间[l,r]中选出两个相同类型的袜子概率
题解：将[l,r]按l分块，那么每次对一个块内的所有询问，l的下标移动是\(\sqrt{n}\)的r的下标移动是n的，总体复杂度n\(\sqrt{n}\)
优化：将偶数块的r按从小到大排序，奇数块从大道小排序可以减少r移动的次数
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 50010,Ba = 200;
int c[N],cnt[N];
ll ans[N][2];
vector<array<int,3>> qu;
void solve()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i) cin>>c[i];
for(int i=1;i<=m;++i)
{
int l,r;
cin>>l>>r;
//需要特判空区间,防止出现re
if(l == r) {ans[i][0] = 0,ans[i][1] = 1;continue;}
qu.push_back({l,r,i});
//(l~r)总选择的情况
ans[i][1] = (ll)(r-l+1)*(r-l)/2;
}
sort(qu.begin(),qu.end(),[&](array<int,3> A,array<int,3> B)
{
if(A[0]/Ba!=B[0]/Ba) return (A[0]/Ba < B[0]/Ba);
//若块为奇数就反序排列，块为偶数r从小到达排列
if((A[0]/Ba) & 1) return (A[1]>B[1]);
else return (A[1]<B[1]);
});
ll tmp = 0;
//每新加进来一个数,可以成对的情况就多出cnt[c[x]]种
auto add = [&](int x)->void
{
//添加的时候应该先加入tmp在自增cnt
tmp += cnt[c[x]]++;
};
auto del = [&](int x)->void
{
//删除的时候应该先减小cnt在减去tmp
tmp -= --cnt[c[x]];
};
int l = 1, r = 0;
for(auto q:qu)
{
int x = q[0], y = q[1];
int id = q[2];
while(r < y) r++, add(r);
while(l > x) l--, add(l);
while(r > y) del(r), r--;
while(l < x) del(l), l++;
int G = __gcd(tmp,ans[id][1]);
ans[id][0] = tmp/G;
ans[id][1] = ans[id][1]/G;
}
for(int i=1;i<=m;++i)
{
cout<<ans[i][0]<<'/'<<ans[i][1]<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
}
重复的数
题意：给定n个数 有m次询问 每次询问[l,r]里有多少个数的出现次数恰好为k
题解：莫队，维护区间每个数出现的次数以及区间内出现该次数的数字个数
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 1e5+10,Ba = 500;
int a[N],cnt[N],fre[N];
int ans[N];
vector<array<int,4>> qu;
void solve()
{
int n,m;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
cin>>m;
for(int i=1;i<=m;++i)
{
int l,r,k;
cin>>l>>r>>k;
qu.push_back({l,r,k,i});
}
sort(qu.begin(),qu.end(),[&](array<int,4> A,array<int,4> B)
{
if(A[0]/Ba!=B[0]/Ba) return (A[0]/Ba < B[0]/Ba);
//若块为奇数就反序排列，块为偶数r从小到达排列
if((A[0]/Ba) & 1) return (A[1]>B[1]);
else return (A[1]<B[1]);
});
//记录每个出现频率的数
auto add = [&](int x)->void
{
//增加的时候原本和a[x]的同频的个数减小，频数加一的个数加一
fre[cnt[a[x]]]--;
fre[++cnt[a[x]]]++;
};
auto del = [&](int x)->void
{
fre[cnt[a[x]]]--;
fre[--cnt[a[x]]]++;
};
int l = 1, r = 0;
for(auto q:qu)
{
int x = q[0], y = q[1], k = q[2];
int id = q[3];
while(r < y) r++, add(r);
while(l > x) l--, add(l);
while(r > y) del(r), r--;
while(l < x) del(l), l++;
ans[id] = fre[k];
}
for(int i=1;i<=m;++i)
{
cout<<ans[i]<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T = 1;
//cin>>T;
while(T--)
{
solve();
}
}
启发式合并
梦幻布丁
注意e[x].clear()不释放内存，可以用vector().swap(e[x])释放，swap时间复杂度是O(1)的
#include<bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
vector<int> e[M];
int color[N];
int ans;
void add(int u, int v)
{
e[u].push_back(v);
}
void merge(int x, int y)
{
if (x == y) return;
if (e[x].size() > e[y].size()) e[x].swap(e[y]);
//保证是从x合并到y
int col = color[e[y][0]];
for (auto v:e[x])
{
//若有相邻则段数减一
ans -= (color[v - 1] != color[v]) + (color[v + 1] != color[v]);
color[v] = col;
ans += (color[v - 1] != color[v]) + (color[v + 1] != color[v]);
}
for (auto v:e[x])
{
e[y].push_back(v);
}
vector<int>().swap(e[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for (int i = 1; i <= n; i ++ )
{
cin>>color[i];
//把0和n+1考虑进来
if (color[i] != color[i - 1]) ans ++;
add(color[i], i);
}
ans++;
//cout<<ans<<'\n';
while (m -- )
{
int op;
cin>>op;
if (op == 2) cout<<ans-1<<'\n';
else
{
int x, y;
cin>>x>>y;
merge(x, y);
}
}
return 0;
}