线段树维护的各种信息¶
例题 #1 开方¶
上帝造题的七分钟 2 / 花神游历各国
输入格式
第一行一个整数 \(n\)，代表数列中数的个数。
第二行 \(n\) 个正整数，表示初始状态下数列中的数。
第三行一个整数 \(m\)，表示有 \(m\) 次操作。
接下来 \(m\) 行每行三个整数 k l r。
-
\(k=0\) 表示给 \([l,r]\) 中的每个数开平方（下取整）。
-
\(k=1\) 表示询问 \([l,r]\) 中各个数的和。
数据中有可能 \(l>r\)，所以遇到这种情况请交换 \(l\) 和 \(r\)。
对于 \(30\%\) 的数据，\(1\le n,m\le 10^3\)，数列中的数不超过 \(32767\)。
对于 \(100\%\) 的数据，\(1\le n,m\le 10^5\)，\(1\le l,r\le n\)，数列中的数大于 \(0\)，且不超过 \(10^{12}\)。
是否可以改成pushdown形？？→会有取整问题，不行
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ps second
#define pf first
#define rd read()
inline int read()
{
int xx=0,ff=1;
char c=getchar();
while(c<'0'||c>'9') {if(c=='-') ff=-1;c=getchar();}
while(c>='0'&&c<='9') xx=xx*10+(c-'0'),c=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
const int N = 2e6+6;
const int INF=1e9+5;
const int MOD=998244353;
int n,m;
int a[N];
int tag[N];
struct node{
int sum,mx;
}tr[N];
void pushup(int x){
tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
tr[x].mx=max(tr[x<<1].mx,tr[x<<1|1].mx);
}
// void addtag(int x,int tg){
// tag[x]+=tg;
// int res=tg;
// while(res&&tr[x].mx>1){
// tr[x].sum=sqrt(tr[x].sum);
// tr[x].mx=sqrt(tr[x].mx);
// res--;
// }
// }
// void pushdown(int x){
// addtag(x<<1,tag[x]);
// addtag(x<<1|1,tag[x]);
// tag[x]=0;
// }
void change(int x,int l,int r,int pl,int pr){
if(tr[x].mx<2)return ;
if(l==r){
// addtag(x,1);
tr[x].sum=sqrt(tr[x].sum);
tr[x].mx=sqrt(tr[x].mx);
return ;
}
// pushdown(x);
int mid=l+r>>1;
if(pl<=mid)change(x<<1,l,mid,pl,pr);
if(pr>mid)change(x<<1|1,mid+1,r,pl,pr);
pushup(x);
}
int query(int x,int l,int r,int pl,int pr){
if(l>=pl&&r<=pr){
return tr[x].sum;
}
// pushdown(x);
int mid=l+r>>1;
int res=0;
if(pl<=mid)res+=query(x<<1,l,mid,pl,pr);
if(pr>mid)res+=query(x<<1|1,mid+1,r,pl,pr);
return res;
}
void build(int x,int l,int r){
if(l==r){
tr[x]={a[l],a[l]};
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
signed main(){
n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
build(1,1,n);
m=rd;
while(m--){
int k=rd,l=rd,r=rd;
if(l>r)swap(l,r);
if(k){
cout<<query(1,1,n,l,r)<<endl;
}else{
change(1,1,n,l,r);
}
}
}
例题 #2 连续序列统计¶
2024暑假S组专题3-数据结构1-ctree/SGTJ. Black And White
题目描述¶
给你一个长度为n的01序列 a[1],...,a[n]
每次询问给定一个区间[l,r]，询问[l,r]里最长的连续的1的长度
每次修改给定一个区间[l,r]，将[l,r]里的a[i]变成1-a[i]（或者说异或1）
n, m <= 100000
输入格式¶
第一行一个n
第二行n个数，表示01序列初始状态
第三行一个m，接下来m行，每行有三个数x,l,r
若 x=0，表示一次查询，查询[l,r]里的最长连续1的长度 若 x=1，表示一次修改，将[l,r]里的数异或1
输出格式¶
对于输入里的每一个查询，输出一行一个整数，该询问的最长连续1的长度。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int a[N];
namespace SGT{
struct node{
int len;
int ml[2],mr[2];
int mx[2];
}t[N<<2];
int tag[N<<2];
node merge(node a,node b){
node r;
for(int i=0;i<=1;i++){
r.ml[i]=max(a.ml[i],a.mx[i]==a.len?a.mx[i]+b.ml[i]:-INF);
r.mr[i]=max(b.mr[i],b.mx[i]==b.len?b.mx[i]+a.mr[i]:-INF);
r.mx[i]=max(max(a.mx[i],b.mx[i]),a.mr[i]+b.ml[i]);
}
r.len=a.len+b.len;
return r;
}
void addtag(int x){
tag[x]^=1;
swap(t[x].mx[1],t[x].mx[0]);
swap(t[x].ml[1],t[x].ml[0]);
swap(t[x].mr[1],t[x].mr[0]);
}
void pushdown(int x){
if(!tag[x])return ;
addtag(x<<1);
addtag(x<<1|1);
tag[x]=0;
}
void pushup(int x){
t[x]=merge(t[x<<1],t[x<<1|1]);
}
void change(int x,int l,int r,int pl,int pr){
if(pl<=l&&pr>=r){
addtag(x);
return ;
}
pushdown(x);
int mid=l+r>>1;
if(pl<=mid)change(x<<1,l,mid,pl,pr);
if(pr>mid)change(x<<1|1,mid+1,r,pl,pr);
pushup(x);
}
node query(int x,int l,int r,int pl,int pr){
if(pl<=l&&pr>=r){
return t[x];
}
pushdown(x);
int mid=l+r>>1;
int fl=0,fr=0;
node nl,nr;
if(pl<=mid)fl=1,nl=query(x<<1,l,mid,pl,pr);
if(pr>mid)fr=1,nr=query(x<<1|1,mid+1,r,pl,pr);
if(fl+fr==1){
if(fl)return nl;
return nr;
}
return merge(nl,nr);
}
void build(int x,int l,int r){
if(l==r){
t[x].len=1;
for(int i=0;i<=1;i++){
t[x].ml[i]=(i==a[l]);
t[x].mr[i]=(i==a[l]);
t[x].mx[i]=(i==a[l]);
}
return ;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
}using namespace SGT;
void solve(){
int n=rd;
for(int i=1;i<=n;i++){
a[i]=rd;
}
int m=rd;
build(1,1,n);
while(m--){
int op=rd,l=rd,r=rd;
if(op){
change(1,1,n,l,r);
}else{
cout<<query(1,1,n,l,r).mx[1]<<endl;
}
}
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}
例题 #3 区间翻转¶
区间翻转问题一般是使用平衡树。但是本题具有特殊性质（即所有可能的翻转区间要么无交、要么包含），因此可以使用线段树维护。具体而言，这个时候如果区间翻转，就交换左右儿子并打上 tag。pushdown 时如果有 tag 就交换分别交换左右儿子的左右儿子，然后把 tag 传给儿子们即可。
/*////////ACACACACACACAC///////////
. Code by Ntsc .
. Earn knowledge .
/*////////ACACACACACACAC///////////
#include<bits/stdc++.h>
#define int long long
#define db double
#define rtn return
using namespace std;
const int N=1e6+1e5;
const int M=1e5;
const int Mod=1e5;
const int INF=1e5;
int n,m,q,T,a[N],res[N],b[N],ans,lim,tp;
int rev[22][N],ls[N],rs[N],f[2][22][N],dep[N<<1];
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int rd() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using GTR::rd;
void addtag(int x,int tg){
if(tg==n)return ;
for(int i=tg;i<n;i++){
rev[i][x]^=1;
swap(f[0][i][x],f[1][i][x]);
}
if(tg!=dep[x])return ;
rev[tg][x]^=1;
swap(ls[x],rs[x]);
}
void pushdown(int x){
for(int i=dep[x]+1;i<n;i++){
if(!rev[i][x])continue;
rev[i][x]=0;//标记旋转
rev[i][ls[x]]^=1;
rev[i][rs[x]]^=1;
swap(f[0][i][ls[x]],f[1][i][ls[x]]);
swap(f[0][i][rs[x]],f[1][i][rs[x]]);
if(i>dep[x]+1)continue;
rev[i][ls[x]]^=1;
rev[i][rs[x]]^=1;
swap(ls[ls[x]],rs[ls[x]]);
swap(ls[rs[x]],rs[rs[x]]);
}
}
void pushup(int x){
for(int i=dep[x]+1;i<n;i++){
f[0][i][x]=f[0][i][ls[x]]+f[0][i][rs[x]];
f[1][i][x]=f[1][i][ls[x]]+f[1][i][rs[x]];
}
}
//void build(int x,int l,int r){
// if(l==r){
//
// }
// int mid=l+r>>1;
// build(ls[x],l,mid);
// build(rs[x],mid+1,r);
// pushup(x);
//}
void change(int x,int l,int r,int pl,int pr,int v){
if(r<=pl||l>=pr)return ;
if(l>=pl&&r<=pr){
return addtag(x,v);
}
pushdown(x);
int mid=l+r>>1;
change(ls[x],l,mid,pl,pr,v);
change(rs[x],mid,r,pl,pr,v);//不是mid+1
pushup(x);
}
void init(int x,int l,int r){
if(l==r-1)return;int mid=(l+r)/2;
ls[x]=x<<1;rs[x]=x<<1|1;
dep[ls[x]]=dep[x]+1;
init(ls[x],l,mid);
dep[rs[x]]=dep[x]+1;
init(rs[x],mid,r);
for(int j=mid,i=l,k=l;;j++){
if(j==r){
while(i<mid)
b[k++]=a[i++];
break;
}
while(i<mid&&a[i]<=a[j])b[k++]=a[i++];
f[0][dep[x]][x]+=mid-i;
b[k++]=a[j];
}
for(int i=l,j=mid;i<mid;i++){
while(j<r&&a[i]>=a[j])j++;
f[1][dep[x]][x]+=r-j;
}
// while(j<=r)
for(int i=l;i<r;i++)a[i]=b[i];
pushup(x);
}
signed main(){
// freopen("pair.in","r",stdin);
// freopen("pair.out","w",stdout);
// cerr<<(int)pow(2,20)<<endl;
// n=rd(),m=rd();
cin>>n>>m;
for(int i=0;i<1<<n;i++){
cin>>a[i];
}
init(1,0,1<<n);//归并排序以及build
// cerr<<"OK\n";
while(m--){ans=0;
int q,l,r;
cin>>q>>l>>r;
change(1,0,1<<n,(l-1)<<(n-q),r<<(n-q),q);
int res=0;
for(int i=0;i<n;i++)res+=f[0][i][1];
cout<<res<<endl;
}
return 0;
}