目录
线段树是十分有用的工具
我们在用他的时候要简化为问题为简单模型
这样能得心应手
1.区间类型
旅馆线段树
#include <bits/stdc++.h>
using namespace std;
const int N=50010;
struct code
{
int l,r;//表示左右边界
int d,ld,rd;//表示这个区间最长连续的以及左右端点连续的数量
int add;//表示懒标记
}tr[N*4];
int n,m;
void pushup(code&u,code&l,code&r)
{
u.ld = l.ld;
if(l.d == l.r - l.l + 1) u.ld = l.d + r.ld;
u.rd = r.rd;
if(r.d == r.r - r.l + 1) u.rd = r.d + l.rd;
u.d = max(l.d, r.d);
u.d = max(u.d, l.rd + r.ld);
}
void pushup(int u)
{
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void pushdown(code&u,code&left,code&right)
{
if(u.add==1)//表示空出来的位置
{
left.d=left.ld=left.rd=left.r-left.l+1;
right.d=right.ld=right.rd=right.r-right.l+1;
}
else if(u.add==2) //表示不可以住人了
{
left.d=left.ld=left.rd=0;
right.d=right.ld=right.rd=0;
}
left.add=right.add=u.add;//标记继承
u.add=0;//标记清空
}
void pushdown(int u)
{
if(tr[u].add) pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
if(l==r) tr[u]={l,r,1,1,1,0};//表示一个元素
else
{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int l,int r,int v)
{
if(tr[u].l>=l&&tr[u].r<=r)// 找到包含元素
{
if(v==1)//表示入住
{
int ans=tr[u].r-tr[u].l+1;// 表示住满了
tr[u].ld=tr[u].rd=tr[u].d=ans;
}
else
{
tr[u].ld=tr[u].rd=tr[u].d=0;
}
tr[u].add=v;//表示标记
return ;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,v);
if(r>mid) modify(u<<1|1,l,r,v);
pushup(u);//表示被修改之后的答案是什么
}
int query(int u,int len)
{
if(tr[u].l==tr[u].r&&tr[u].d==1&&len==1) return tr[u].l;
if(tr[u].d<len) return 0;
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
if(tr[u<<1].d>=len) return query(u<<1,len);
if(tr[u<<1].rd+tr[u<<1|1].ld>=len) return tr[u<<1].r-tr[u<<1].rd+1;
if(tr[u<<1|1].d>=len) return query(u<<1|1,len);
return 0;
}
int main ()
{
cin>>n>>m;
build(1,1,n);
while(m--)
{
int op,l,r; cin>>op;
if(op==1)
{
cin>>l;
int st=query(1,l);
cout<<st<<endl;
if(st) modify(1,st,st+l-1,2);
}
else
{
cin>>l>>r;
modify(1,l,l+r-1,1);
}
}
return 0;
}
最长连续相同字符
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
struct SEG{
int l,r,len;
char ch;
};
struct code{
int l,r;
SEG maxl,maxr,maxn;
}tr[4*N];
int n,m;
char s[N];
SEG max(SEG&a,SEG&b){
if(a.len==b.len) return a.l<b.l?a:b;
return a.len>b.len?a:b;
}
void pushup(code&u,code&l,code&r){
u.maxl=l.maxl;
if(l.maxl.r==l.r&&l.maxl.ch==r.maxl.ch){// 表示左边全部都是一样的且和右边连起来
u.maxl={l.maxl.l,r.maxl.r,r.maxl.r-l.maxl.l+1,l.maxl.ch};
}
u.maxr=r.maxr;
if(r.maxr.l==r.l&&r.maxr.ch==l.maxr.ch){
u.maxr={l.maxr.l,r.maxr.r,r.maxr.r-l.maxr.l+1,r.maxr.ch};
}
u.maxn=max(l.maxn,r.maxn);
if(l.maxr.ch==r.maxl.ch){
SEG t={l.maxr.l,r.maxl.r,r.maxl.r-l.maxr.l+1,r.maxl.ch};
u.maxn=max(u.maxn,t);
}
}
void pushup(int u){
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,l,{l,l,1,s[l]},{l,l,1,s[l]},{l,l,1,s[l]}};
return ;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int x,char v){
if(tr[u].l==x&&tr[u].r==x){
tr[u]={x,x,{x,x,1,v},{x,x,1,v},{x,x,1,v}};
return ;
}
int mid=tr[u].l+tr[u].r>>1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
code query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
int mid=tr[u].l+tr[u].r>>1;
if(l>mid) return query(u<<1|1,l,r);
else if(r<=mid) return query(u<<1,l,r);
else{
code res;
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
pushup(res,left,right);
return res;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>s[i];
build(1,1,n);
while(m--){
int op,l,r;
cin>>op;
if(op==1){
cin>>l>>r;
code res=query(1,l,r);
cout<<res.maxn.l<<" "<<res.maxn.r<<endl;
}
else{
int x; char v; cin>>x>>v;
modify(1,x,v);
}
}
return 0;
}
2.用划分的维护求变化形的线段树
发工资
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200010,mod=998244353;
struct code{
int l,r;
LL sum1,sum2;
LL add1,add2;// sum1 表示的是总和 // sum2 表示的是差值
}tr[4*N];
int n,m,T;
void push(code&u,code&l,code&r){// 表示计算区间和
u.sum1=(l.sum1+r.sum1)%mod;
u.sum2=(l.sum2+r.sum2)%mod;
}
void push(int u){
push(tr[u],tr[u<<1],tr[u<<1|1]);
}
void down(code&u,code&l,code&r){
l.add1=(l.add1+u.add1)%mod,r.add1=(r.add1+u.add1)%mod;
l.sum1=(l.sum1+(l.r-l.l+1)%mod*u.add1%mod)%mod;
r.sum1=(r.sum1+(r.r-r.l+1)%mod*u.add1%mod)%mod;
l.add2=(l.add2+u.add2)%mod,r.add2=(r.add2+u.add2)%mod;
l.sum2=(l.sum2+(l.r-l.l+1)%mod*u.add2%mod)%mod;
r.sum2=(r.sum2+(r.r-r.l+1)%mod*u.add2%mod)%mod;
u.add1=u.add2=0;
}
void down(int u){
down(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,(LL)0,(LL)0,(LL)0,(LL)0};
return ;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
push(u);
}
void modify(int u,int l,int r,int v){
if(tr[u].l>=l&&tr[u].r<=r){
tr[u].add1=(tr[u].add1+v)%mod;
tr[u].add2=(tr[u].add2+(LL)v*(T-1)%mod)%mod;
tr[u].sum1=(tr[u].sum1+(LL)(tr[u].r-tr[u].l+1)%mod*v%mod)%mod;
tr[u].sum2=(tr[u].sum2+(LL)(T-1)*(tr[u].r-tr[u].l+1)%mod*v%mod)%mod;
return ;
}
down(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,v);
if(r>mid) modify(u<<1|1,l,r,v);
push(u);
}
code query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u];
}
int mid=tr[u].l+tr[u].r>>1;
down(u);
if(r<=mid) return query(u<<1,l,r);
else if(l>mid) return query(u<<1|1,l,r);
else{
code res;
code left=query(u<<1,l,r);
code right=query(u<<1|1,l,r);
push(res,left,right);
return res;
}
}
int main(){
cin>>n>>m;
build(1,1,n);
for(T=1;T<=m;T++){
int op,l,r,d;
cin>>op>>l>>r;
if(!op){
cin>>d;
d%=mod;
modify(1,l,r,d);
}
else{
code res=query(1,l,r);
int y=(LL)res.sum1*T%mod;
int x=res.sum2;
int ans=(y-x+mod)%mod;
cout<<ans<<endl;
}
}
return 0;
}
3位运算类型
Middle
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
struct code{
int l,r;
int w[21][2];// 2 进制的操作
}tr[N*4];
char s[N];
int a[N];
int n,m;
void pushup(code&u,code&l,code&r){
for(int i=0;i<=20;i++)
for(int j=0;j<2;j++){
u.w[i][j]=r.w[i][l.w[i][j]];
}
}
void pushup(int u){
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r};
for(int i=0;i<=20;i++)
for(int j=0;j<2;j++){
int x=a[l]>>i&1;
if(s[l]=='|') tr[u].w[i][j]=x|j;
else if(s[l]=='&') tr[u].w[i][j]=x&j;
else tr[u].w[i][j]=x^j;
}
return ;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int pos,int v){
if(tr[u].l==pos&&tr[u].r==pos){
for(int i=0;i<=20;i++)
for(int j=0;j<2;j++){
int x=v>>i&1;
if(s[pos]=='|') tr[u].w[i][j]=x|j;
else if(s[pos]=='&') tr[u].w[i][j]=x&j;
else tr[u].w[i][j]=x^j;
}
return ;
}
int mid=tr[u].l+tr[u].r>>1;
if(pos<=mid) modify(u<<1,pos,v);
else modify(u<<1|1,pos,v);
pushup(u);
return ;
}
code query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
int mid=tr[u].l+tr[u].r>>1;
if(l>mid) return query(u<<1|1,l,r);
else if(r<=mid) return query(u<<1,l,r);
else{
code res;
auto left=query(u<<1,l,r);
auto right=query(u<<1|1,l,r);
pushup(res,left,right);
return res;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
cin>>m;
while(m--){
int op,l,r,v;
cin>>op;
if(op==1){
cin>>l>>v;
modify(1,l,v);
}
else{
cin>>v>>l>>r;
code res=query(1,l,r);
int sum=0;
for(int i=0;i<=20;i++){
int u=v>>i&1;
sum+=(1ll<<i)*res.w[i][u];
}
cout<<sum<<endl;
}
}
return 0;
}
4维护有效信息
维护有效的信息
对于区间修改,区间查询的线段树我们使用的是对有效信息的维护,如果信息是无效的就不需要维护
所以所我们要在这样的条件下依据不同的题目发现有效信息简化问题而不是直接霸王硬上弓
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x) fixed<<setprecision(x)// c++ 保留小数
#define lu u<<1
#define ru u<<1|1
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,F=2*N,INF=0x3f3f3f3f,pp=13331,mod=1e9+7;
const double pai=acos(-1.0);// pai
int t,n,m,pos;
int a[N];
struct code{
int l,r;
int cnt[3];
int lazy;
}tr[4*N];
void pushup(int u){
for(int i=0;i<3;i++){
tr[u].cnt[i]=tr[u<<1].cnt[i]+tr[u<<1|1].cnt[i];
}
}
void pushdown(code&u,code&l,code&r){
if(u.lazy){
l.lazy=r.lazy=u.lazy;
u.lazy--;
for(int i=0;i<3;i++){
if(i==u.lazy){
l.cnt[i]=l.r-l.l+1;
r.cnt[i]=r.r-r.l+1;
}
else r.cnt[i]=l.cnt[i]=0;
}
}
u.lazy=0;
}
void pushdown(int u){
pushdown(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r};
tr[u].cnt[a[l]]++;
return ;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void modify(int u,int l,int r,int v){
if(l>r) return ;
if(tr[u].l>= l and tr[u].r<=r){
for(int i=0;i<3;i++){
if(i==v){
tr[u].cnt[i]=tr[u].r-tr[u].l+1;
}
else tr[u].cnt[i]=0;
}
tr[u].lazy=v+1;
return ;
}
pushdown(u);
int mid=tr[u].l+tr[u].r>>1;
if(l<=mid) modify(u<<1,l,r,v);
if(r>mid) modify(u<<1|1,l,r,v);
pushup(u);
}
int query(int u,int l,int r,int v){
if(tr[u].l>=l and tr[u].r<=r){
return tr[u].cnt[v];
}
int mid=tr[u].l+tr[u].r>>1;
pushdown(u);
int sum=0;
if(mid>=l) sum=query(u<<1,l,r,v);
if(r>mid) sum+=query(u<<1|1,l,r,v);
return sum;
}
void solve()
{
cin>>n>>m>>pos;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(i==pos) continue;
if(a[i]<a[pos]) a[i]=0;
else if(a[i]==a[pos]) a[i]=1;
else a[i]=2;
}
a[pos]=1;
build(1,1,n);
while(m--){
int op,l,r; cin>>op>>l>>r;
int now0=query(1,l,r,0);
int now1=query(1,l,r,1);
int now2=query(1,l,r,2);
if(op==1){// 需要变成递增的序列
if(pos>=l and pos<=r){//如果在里面的话
int state=query(1,l,pos,1);// 找到其中[l,pos] 1 的数量
pos=l+now0+state-1;// 前面0的数量加上1 的数量
}
modify(1,l,l+now0-1,0);
modify(1,l+now0,l+now0+now1-1,1);
modify(1,r-now2+1,r,2);
}
else{// 需要变成递减序列
if(pos>=l and pos<=r){
int state=query(1,l,pos,1);
pos=l+now2+state-1;
}
modify(1,r-now0+1,r,0);
modify(1,l+now2,r-now0,1);
modify(1,l,l+now2-1,2);
}
cout<<pos<<endl;
}
return ;
}
signed main ()
{
ios
solve();
}