维护区间连续信息
前言
这类题目一般维护区间中连续的信息，例如最长子段和，01串中区间最长1，或者区间里面最长连续单调递增序列等等。常规套路是通过维护区间最左和最右端，然后合并 。
最长子段和
C - Can you answer these queries III
题意：
求一个区间的最大连续和。0表示把A[x]改成y，1 表示求[x,y]这个区间的最大连续和。
思路：
老套路，详细看代码。
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=1e5+7;
int n,m,a[N];
struct node{
int lm,rm,sm,mx;
}tr[4*N];
node merge(node L,node R){
node M;
M.lm=max(L.lm,L.sm+R.lm);
M.rm=max(R.rm,R.sm+L.rm);
M.mx=max({L.mx,R.mx,M.lm,M.rm,L.rm+R.lm});
M.sm=L.sm+R.sm;
return M;
}
void pushup(int k){
tr[k]=merge(tr[lch],tr[rch]);
}
void build(int k,int l,int r){
if(l==r){
tr[k].lm=tr[k].rm=tr[k].sm=tr[k].mx=a[l];
return;
}
build(lch,l,mid);
build(rch,mid+1,r);
pushup(k);
}
node query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[k];
}
if(qr<=mid) return query(lch,l,mid,ql,qr);
else if(ql>mid) return query(rch,mid+1,r,ql,qr);
else return merge(query(lch,l,mid,ql,qr),query(rch,mid+1,r,ql,qr));
}
void update(int k,int l,int r,int p,int v){
if(l==r){
tr[k].lm=tr[k].rm=tr[k].sm=tr[k].mx=v;
return;
}
if(p<=mid){
update(lch,l,mid,p,v);
}else{
update(rch,mid+1,r,p,v);
}
pushup(k);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
scanf("%d",&m);
while(m--){
int op,l,r;
scanf("%d %d %d",&op,&l,&r);
if(op==0){
update(1,1,n,l,r);
}else{
printf("%d\n",query(1,1,n,l,r).mx);
}
}
}01串中维护区间最长连续的1
题意：
给你长度为n的01串，一开始全为1，m次操作
操作一：找最靠左端的连续长度为x的全为1，输出最左端编号，之后修改为0，若不存在，输出0。
操作二：区间x，y全部修改为1。
思路：
首先要找到最靠右端全为1的编号，我们可以想二分,我们观察[1,x]，x和最长连续1的长度具有单调性，之后我们需要维护区间最长连续1（具体维护看代码），这个我们是可以用线段树维护出来，之后二分我们也能再线段树上二分。
代码：
#include <iostream>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=1e5+7;
int n,m;
int len[4*N],sum[4*N],lmx[4*N],rmx[4*N],lz[4*N];
//sum区间最长连续空房的长度
//lmx从l端点开始最长连续空房的长度
//rmx从r端点开始最长连续空房的长度
//lazy为1表示退房，为2表示开房
//区间长度，记录后方便计算
void init(int k,int l,int r){
sum[k]=len[k]=lmx[k]=rmx[k]=r-l+1;
lz[k]=-1;
if(l==r){
return;
}
init(lch,l,mid);
init(rch,mid+1,r);
}
void pushup(int k){
lmx[k]=(lmx[lch]==len[lch])? lmx[lch]+lmx[rch]:lmx[lch];
//若左儿子区间全空那么lmax可以横跨左右儿子，否则不能
rmx[k]=(rmx[rch]==len[rch])? rmx[rch]+rmx[lch]:rmx[rch];
//若右儿子区间全空那么rmax可以横跨左右儿子，否则不能
sum[k]=max(rmx[lch]+lmx[rch],max(sum[lch],sum[rch]));
//有三种情况，sum全在左儿子，全在右儿子，横跨左右儿子
}
void pushdown(int k){
if(lz[k]!=-1){
//下传lazy标记
lz[lch]=lz[rch]=lz[k];
sum[lch]=lmx[lch]=rmx[lch]=len[lch]*lz[k];
sum[rch]=lmx[rch]=rmx[rch]=len[rch]*lz[k];
lz[k]=-1;
}
}
//区间赋值0/1
void update(int k,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
lmx[k]=rmx[k]=sum[k]=len[k]*val;
lz[k]=val;
return;
}
pushdown(k);
if(ql<=mid) update(lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(rch,mid+1,r,ql,qr,val);
pushup(k);
}
//寻找最左边大于等于x的线段
int query(int k,int l,int r,int x){
if(l==r) return l;
pushdown(k);
if(sum[lch]>=x) return query(lch,l,mid,x);
//递归到左儿子
else if(rmx[lch]+lmx[rch]>=x) return mid-rmx[lch]+1;
//左右儿子合并后满足就用中间
else return query(rch,mid+1,r,x);
//递归到右儿子
}
int ask(int k,int l,int r,int p){
if(l==r) return sum[k];
pushdown(k);
if(p<=mid) return ask(lch,l,mid,p);
else return ask(rch,mid+1,r,p);
}
int main(){
cin>>n>>m;
init(1,1,n);
while(m--){
int op,x,y;
cin>>op;
if(op==1){
cin>>x;
if(sum[1]>=x){
int pos=query(1,1,n,x);
cout<<pos<<"\n";
update(1,1,n,pos,pos+x-1,0);
}else{
cout<<"0\n";
}
}else{
cin>>x>>y;
update(1,1,n,x,x+y-1,1);
}
}
}
区间单调连续序列数量
题意：
给你个序列$a_i$，m次操作，点单修改，区间询问有多少单调不减连续序列。
思路：
问有多少连续单调不减，考虑线段树，我们可以维护个靠左端点单调不减长度Lx，右端点单调不减长度Rx，和区间最长单调不见mx，如果线段树要pushup，要将左右子树合并，在需要维护左端点的数，和右端点的树即可完成线段树操作。
代码：
#include <iostream>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=2e5+10;
int n,m,a[N];
struct node{
int lx,rx,lv,rv,len;
ll s;
}tr[4*N];
node merge(node LC,node RC){
node RT;
if(LC.rv<=RC.lv){
RT.s=LC.s+RC.s+1ll*LC.rx*RC.lx;
if(LC.lx==LC.len)
RT.lx=LC.lx+RC.lx;
else RT.lx=LC.lx;
if(RC.rx==RC.len) RT.rx=RC.rx+LC.rx;
else RT.rx=RC.rx;
}
else{
RT.s=LC.s+RC.s;
RT.lx=LC.lx;
RT.rx=RC.rx;
}
RT.lv=LC.lv,RT.rv=RC.rv;
RT.len=LC.len+RC.len;
return RT;
}
void pushup(int k){
tr[k]=merge(tr[lch],tr[rch]);
}
void init(int k,int l,int r){
tr[k].len=r-l+1;
if(l==r){
tr[k].lv=tr[k].rv=a[l];
tr[k].lx=tr[k].rx=1;
tr[k].s=1;
return;
}
init(lch,l,mid);
init(rch,mid+1,r);
pushup(k);
}
void update(int k,int l,int r,int p,int v){
if(l==r){
tr[k].lv=tr[k].rv=v;
tr[k].lx=tr[k].rx=1;
tr[k].s=1;
return;
}
if(p<=mid) update(lch,l,mid,p,v);
else update(rch,mid+1,r,p,v);
pushup(k);
}
node query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[k];
}
if(qr<=mid) return query(lch,l,mid,ql,qr);
else if(ql>mid) return query(rch,mid+1,r,ql,qr);
else return merge(query(lch,l,mid,ql,qr),query(rch,mid+1,r,ql,qr));
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
init(1,1,n);
while(m--){
int op,x,y;
scanf("%d %d %d",&op,&x,&y);
if(op==1){
update(1,1,n,x,y);
}else{
printf("%lld\n",query(1,1,n,x,y).s);
}
}
}维护区间复杂信息
维护最长递增序列
题意：
给你n个序列，待修，问其从[1,n]的斜率单调递增序列。
思路：
既然是单调递增，那么我们线段树的每一个节点可以维护这个节点所对应的区间的最大值，与从这段区间开头可以看到的区间内的所有楼房
那么我们要怎么查询呢？
答案显然是第一个节点（根节点）的答案
所以我们现在的主要问题就是怎么修改
对于每一个叶子节点，从这段区间头可以看到的楼房数量一定为11，区间斜率最大值一定为该点的斜率
那么合并呢？
显然合并区间的所有楼房一定可以看到左边的区间第一个位置看到的所有楼房（这应该很显然吧）
那么右区间呢？
我们可以先查找右区间的左区间的最大值，如果这个最大值比左区间的最大值小，那么有区间的左区间的所有答案一定看不到，所以我们就可以递归查找右区间的右区间
如果右区间的左区间的最大值比左区间的最大值大，那么原来被右区间的左区间挡住的现在一样会被挡住，我们就可以加上右区间的答案，所以我们可以递归查找右区间的左区间
但是这里有一个坑点，有区间的答案不一定是$ans$[右区间的右区间]，因为右区间的答案可能被左区间挡住，所以有区间的答案一定是$ans$[右区间]-$ans$[右区间的左区间]
每次查询的复杂度为$O(1)$，我们每次只会递归一个儿子，所以每次查询右儿子答案的复杂度为$O(logn)$，故每次修改的复杂度为$O(log2n)$
代码：
#include <iostream>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=1e5+10;
double mx[4*N];
int n,m,tr[4*N];
double query(int k,int l,int r,double v){
if(mx[k]<=v){
return 0;
}
if(l==r){
return mx[k]>v;
}
if(mx[lch]<=v){
return query(rch,mid+1,r,v);
}else {
return query(lch,l,mid,v)+tr[k]-tr[lch];
}
}
void motify(int k,int l,int r,int p,double v){
if(l==r){
mx[k]=v,tr[k]=1;
return;
}
if(p<=mid) motify(lch,l,mid,p,v);
else motify(rch,mid+1,r,p,v);
mx[k]=max(mx[lch],mx[rch]);
tr[k]=tr[lch]+query(rch,mid+1,r,mx[lch]);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d %d",&x,&y);
motify(1,1,n,x,(double)y/x);
printf("%d\n",tr[1]);
}
}
板子：
兔对线段树用查询 查询[ l , r ]，从$l$ 开始到左边第一个大于$x$的值$x_1$ 左边第一个大于$x_1$的值……的最长序列是多少。
const int N = 1e5 + 7;
struct segment {
int maxn, len;
}tree[4 * N];
#define m (l + r) / 2
#define lson 2 * node
#define rson 2 * node + 1
int work(int k, int l, int r, int node) {
if (l == r) return 0;
if (tree[lson].maxn > k) {
return work(k, l, m, lson);
} else {
return work(k, m + 1, r, rson) + tree[node].len - tree[rson].len;
}
}
segment merge (segment x, segment y, int l, int r, int node) {
segment z;
if (x.len == 0) return y;
if (y.len == 0) return x;
z.maxn = max(x.maxn, y.maxn);
if (x.maxn >= y.maxn) {
z.len = x.len;
} else {
z.len = x.len + y.len - work(x.maxn, l, r, node);
}
return z;
}
void update(int pos, int v, int l, int r, int node) {
if (l == r) {
tree[node].maxn = v;
tree[node].len = 1;
return;
}
if (pos <= m) update(pos, v, l, m, lson);
else update(pos, v, m + 1, r, rson);
tree[node] = merge(tree[lson], tree[rson], m + 1, r, rson);
}
segment query(int ql, int qr, int l, int r, int node) {
if (ql <= l && qr >= r) {
return tree[node];
}
segment res;
res.len = 0;
if (ql <= m) res = merge(res, query(ql, qr, l, m, lson), m + 1, r, rson);
if (qr > m) res = merge(res, query(ql, qr, m + 1, r, rson), m + 1, r, rson);
return res;
}
异或区间分段
我们可能看出，$[L_i,R_i]\ xor\ W_i$会被分割成若干个不连续的区间。通过二进制的异或个规律我们可以发现，如果我们建棵$[0，2^{30}-1]$的线段树区间，那么线段树分割的区间将全为连续的区间。那么我们用线段树求出异或后的区间，最后求区间交算答案
#include <iostream>
#include <algorithm>
#include <vector>
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pll;
const int N=1e5+7;
const int S=(1<<30)-1;//建区间为[0,2^30-1]的线段树
struct node{int to,w,next;}e[2*N];
int n,a[N],ll[N],rr[N];
int head[N],tot;
vector <pll> ho,col;
void add(int u,int v,int w){
e[++tot].to=v;
e[tot].w=w;
e[tot].next=head[u];
head[u]=tot;
}
void dfs(int p,int fa){
for(int i=head[p];i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(v==fa) continue;
a[v]=a[p]^w;
dfs(v,p);
}
}
//处理[l,r] xor X
void ikuzo(int l,int r,int d,int x){
//d为有多少位值不同。
int pl=l&(S^((1<<d)-1));
int pe=x&(S^((1<<d)-1));
//分的的区间放入vector
ho.push_back(pll(pe^pl,pe^pl+((1<<d)-1)));
}
//区间[l,r]xor d分成logn段
void update(int l,int r,int ql,int qr,int d,int x){
if(ql<=l&&r<=qr){
ikuzo(l,r,d,x);
return;
}
int mid=(l+r>>1);
if(ql<=mid) update(l,mid,ql,qr,d-1,x);
if(mid+1<=qr) update(mid+1,r,ql,qr,d-1,x);
}
void solve(){
//差分求区间交
for(int i=0;i<ho.size();i++){
col.push_back(pll(ho[i].fi,1));
col.push_back(pll(ho[i].se+1,-1));
}
sort(col.begin(),col.end());
int sum=0,ans=0;
for(int i=0;i+1<col.size();i++){
sum+=col[i].se;
if(sum>=n){
ans+=col[i+1].fi-col[i].fi;
}
}
printf("%d\n",ans);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>ll[i]>>rr[i];
for(int i=1;i<=n-1;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);add(v,u,w);
}
dfs(1,-1);
for(int i=1;i<=n;i++){
update(0,S,ll[i],rr[i],30,a[i]);
}
solve();
}
线段树维护线性基
题意：
给你n个桶，每个桶可以任意单点插值，区间查询桶$[l,r]$的值任挑若干个异或和最大。
思路：典型线段树维护线性基，复杂度为$O(nlogn*32)$
代码：
#include <iostream>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=5e4+10;
int m,n;
struct node{
ll bas[35];
}tr[4*N];
void insert(node &t,ll v){
for(ll i=32;i>=1;i--){
if((v&(1ll<<(i-1)))==0) continue;
if(t.bas[i]){
//若如主元j已经存在，用a[j]消去x的第j位然后继续
v^=t.bas[i];
continue;
}
for(int j=1;j<=i-1;j++){
//让x当主元i，需要先用第j(j<i)个主元消去x的第j位
if(v&(1ll<<(j-1))) v^=t.bas[j];
}
for(int j=i+1;j<=32;j++){
//接着用x去消掉第j(j>i)个主元的第i位
if(t.bas[j]&(1ll<<(i-1))) t.bas[j]^=v;
}
t.bas[i]=v;
return;
}
}
node merge(node L,node R){
node RT=L;
for(int i=1;i<=32;i++){
insert(RT,R.bas[i]);
}
return RT;
}
void update(int k,int l,int r,int p,int v){
insert(tr[k],v);
if(l==r) return;
if(p<=mid) update(lch,l,mid,p,v);
else update(rch,mid+1,r,p,v);
}
node query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[k];
}
if(qr<=mid) return query(lch,l,mid,ql,qr);
else if(ql>mid) return query(rch,mid+1,r,ql,qr);
else return merge(query(lch,l,mid,ql,qr),query(rch,mid+1,r,ql,qr));
}
int main(){
scanf("%d %d",&m,&n);
while(m--){
int op,x,y;
scanf("%d %d %d",&op,&x,&y);
if(op==1){
update(1,1,n,x,y);
}else{
node t=query(1,1,n,x,y);
ll ans=0;
for(int i=1;i<=32;i++){
ans=ans^t.bas[i];
}
printf("%lld\n",ans);
}
}
}
线段树维护哈希
题意：
给你一个长为 $n$ 的序列 $a$
每次两个操作：
- 修改 x 位置的值为 y
- 查询区间 $[l,r]$ 是否可以重排为值域上连续的一段,例如3，4，5，特别的不能有重复元素，例如2，2，3
思路：对于区间维护max,和min就可以确定区间长度，要是其连续，我们可以用线段树哈希两个值，如连续序列的和例如$3+4+5$和平方和$3^2+4^2+5^2$，这几个运算都有公式的，其中第二个公式为$n(n+1)(2n+1)/6$，就能判断是否连续
代码：
#include <iostream>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=5e5+10;
const ll mod=998244353;
struct node{
int mx,mn;
ll s1,s2;
}tr[4*N];
int n,m,a[N];
ll ksm(ll x,ll p){
ll res=1;
while(p){
if(p&1) res=res*x%mod;
x=x*x%mod;
p>>=1;
}
return res;
}
ll inv(ll x){
return ksm(x,mod-2);
}
ll sum1(ll x){
return (1+x)*x%mod*inv(2)%mod;
}
ll sum2(ll x){
return x*(x+1)%mod*(2*x+1)%mod*inv(6)%mod;
}
node merge(node LC,node RC){
node RT;
RT.mx=max(LC.mx,RC.mx);
RT.mn=min(LC.mn,RC.mn);
RT.s1=(LC.s1+RC.s1)%mod;
RT.s2=(LC.s2+RC.s2)%mod;
return RT;
}
void pushup(int k){
tr[k]=merge(tr[lch],tr[rch]);
}
void init(int k,int l,int r){
if(l==r){
tr[k].mx=tr[k].mn=tr[k].s1=a[l];
tr[k].s2=1ll*a[l]*a[l]%mod;
return;
}
init(lch,l,mid);
init(rch,mid+1,r);
pushup(k);
}
void update(int k,int l,int r,int p,int v){
if(l==r){
tr[k].mx=tr[k].mn=tr[k].s1=v;
tr[k].s2=1ll*v*v%mod;
return;
}
if(p<=mid) update(lch,l,mid,p,v);
else update(rch,mid+1,r,p,v);
pushup(k);
}
node query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tr[k];
if(qr<=mid) return query(lch,l,mid,ql,qr);
else if(ql>mid) return query(rch,mid+1,r,ql,qr);
else return merge(query(lch,l,mid,ql,qr),query(rch,mid+1,r,ql,qr));
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
init(1,1,n);
while(m--){
int op,x,y;
scanf("%d %d %d",&op,&x,&y);
if(op==1){
update(1,1,n,x,y);
}else{
node t=query(1,1,n,x,y);
if((t.mx-t.mn==y-x)&&(t.s1==(sum1(t.mx)+mod-sum1(t.mn-1))%mod)&&(t.s2==(sum2(t.mx)+mod-sum2(t.mn-1))%mod)){
puts("damushen");
}else{
puts("yuanxing");
}
}
}
}
扫描线
前言：
扫描线其实就是通过差分，用线段树来维护一段值域，不限于求面积。
矩阵面积：
求坐标中矩阵面积。
思路:
这其实是扫描线经典题，但这种线段树有些特别的地方，例如维护的是长度,例如[1,2,]长度为1，而且这里区修不要$pushdown$
#include <iostream>
#include <vector>
#include <algorithm>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=1e5+7;
struct Segmet{
double x,y1,y2;
int k;
bool operator<(const Segmet &t) const{
return x<t.x;
}
}a[N];
struct node{
int l,r;
int cnt;
double len;
}tr[8*N];
int n,o;
vector <double> ho;
int get(double x){return lower_bound(ho.begin(),ho.end(),x)-ho.begin();}
void build(int k,int l,int r){
tr[k]={l,r,0,0};
if(l==r) return;
build(lch,l,mid);
build(rch,mid+1,r);
}
void pushup(int k){
if(tr[k].cnt) tr[k].len=ho[tr[k].r+1]-ho[tr[k].l];
else tr[k].len=tr[lch].len+tr[rch].len;
}
void update(int k,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
tr[k].cnt+=val;
pushup(k);
return;
}
if(ql<=mid) update(lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(rch,mid+1,r,ql,qr,val);
pushup(k);
}
void solve(){
ho.clear();
for(int i=1;i<=n;i++){
double x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
a[i]={x1,y1,y2,1};
a[n+i]={x2,y1,y2,-1};
ho.push_back(y1),ho.push_back(y2);
}
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
sort(a+1,a+1+2*n);
build(1,0,2*n);
double ans=0;
for(int i=1;i<=2*n;i++){
ans=ans+(a[i].x-a[i-1].x)*tr[1].len;
update(1,0,2*n,get(a[i].y1),get(a[i].y2)-1,a[i].k);
}
printf("Test case #%d\n",++o);
printf("Total explored area: %.2lf\n\n",ans);
}
int main(){
while(cin>>n&&n) solve();
}扫描线维护值域
有 $n$ 个有权值的点，有一个 $H ×W$的矩形，问这个矩形最多可以框住多少权值。
思路：
这里有个技巧，不妨把星星的面积为$H ×W$的矩形，这样我们就能和扫描线一样的操作，从左到右差分，动态的维护一个值域表示覆盖情况，扫描过程中统计值域中max就是答案。
代码：
#include <iostream>
#include <vector>
#include <algorithm>
#define bug cout<<"bug\n"
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=1e5+7;
struct Segmet{
int x,y1,y2,k;
bool operator <(const Segmet &t)const{
if(x==t.x) return k>t.k;
return x<t.x;
}
}seg[N];
ll tr[4*N],lz[4*N];
int T;
int n,m,w,h;
vector <int> ho;
void init(){
ho.clear();
}
int get(int x){return lower_bound(ho.begin(),ho.end(),x)-ho.begin()+1;}
void build(int k,int l,int r){
lz[k]=0;
if(l==r){
tr[k]=0;
return;
}
build(lch,l,mid);
build(rch,mid+1,r);
tr[k]=max(tr[lch],tr[rch]);
}
void pushdown(int k){
if(lz[k]){
lz[lch]+=lz[k];
lz[rch]+=lz[k];
tr[lch]+=lz[k];
tr[rch]+=lz[k];
lz[k]=0;
}
}
void update(int k,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
tr[k]+=val;
lz[k]+=val;
return;
}
pushdown(k);
if(ql<=mid) update(lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(rch,mid+1,r,ql,qr,val);
tr[k]=max(tr[lch],tr[rch]);
}
void solve(){
cin>>n>>w>>h;
init();
for(int i=1;i<=n;i++){
int x,y,l;
cin>>x>>y>>l;
seg[i]={x,y,y+h-1+1,l};
seg[i+n]={x+w-1,y,y+h-1+1,-l};
ho.push_back(y),ho.push_back(y+h-1);
}
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
m=2*n;
sort(seg+1,seg+1+m);
build(1,1,m);
ll ans=0;
for(int i=1;i<=m;i++){
update(1,1,m,get(seg[i].y1),get(seg[i].y2),seg[i].k);
ans=max(ans,tr[1]);
}
cout<<ans<<"\n";
}
int main(){
cin>>T;
while(T--) solve();
}
线段树维护区间覆盖
前言：
区间问题各式各样，但用时我们能用到线段树区间修改和区间查询这优秀的性质来维护，如果区修与区查只用到一个也可以用树状数组。
区间覆盖价值最大值
题意
给你n条线段$t_i,x_i$，其中每个线段都覆盖了$[2kt_i+1,2kt_i+t_i],(k=1,2,3...)$的区域，并且价值为$x_i$，询问在区间$[1,m]$中每个点产生的最大价值。
思路：
首先明白，假设线段的$t_i$相同，那么覆盖的区域是相同的部分，那么完全可以用$x_i$大的代替，这样我们能将n条线段去重，留下的线段$t_i$各不相同，我们区间修改一条线段需要$[\frac{m}{2t_i}]$次，由于$t_i$不同，$\sum[\frac{m}{2t_i}]=mlogm$，区间修改我们能用线段树解决，即复杂度为$O(mlog^2m)$
线段树维护每个点染色的最大值，我们有两种方法。
方法一：对区间按价值$x_i$从小到大排序，然后直接染色即可。（推荐）
方法二：记录懒标记，每次修改原本价值取$max$,懒标记也取$max$记录。
代码一：
方法一
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const int N=1e5+7;
struct node{int t,x;}a[N];
int T,o;
int n,m;
ll tree[4*N],tap[4*N];
int ho[N],tot;
bool cmp(node x,node y){
if(x.t==y.t) return x.x>y.x;
return x.t<y.t;
}
bool cmp1(int x,int y){
return a[x].x<a[y].x;
}
void init(int k,int l,int r){
tap[k]=-1;
if(l==r){
tree[k]=0;
return ;
}
init(lch,l,mid);
init(rch,mid+1,r);
}
void pushdown(int k){
if(tap[k]!=-1){
tree[lch]=tap[k];
tree[rch]=tap[k];
tap[lch]=tap[k];
tap[rch]=tap[k];
tap[k]=-1;
}
}
void update(int k,int l,int r,int ql,int qr,ll val){
if(ql<=l&&r<=qr){
tree[k]=val;
tap[k]=val;
return;
}
pushdown(k);
if(ql<=mid) update(lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(rch,mid+1,r,ql,qr,val);
}
ll qry(int k,int l,int r,int p){
if(l==r){
return tree[k];
}
pushdown(k);
if(p<=mid) return qry(lch,l,mid,p);
else return qry(rch,mid+1,r,p);
}
int main(){
cin>>T;
while(T--){
scanf("%d %d",&n,&m);
tot=0;
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].t,&a[i].x);
}
//去重
sort(a+1,a+1+n,cmp);
int now=-1;
for(int i=1;i<=n;i++){
if(now==a[i].t) continue;
else{
now=a[i].t;
ho[++tot]=i;
}
}
//从小到大染色
sort(ho+1,ho+1+tot,cmp1);
init(1,1,m);
for(int i=1;i<=tot;i++){
int id=ho[i];
for(int k=0;;k++){
int l=2*k*a[id].t+1,r=2*k*a[id].t+a[id].t;
r=min(m,r);
if(l<=m){
update(1,1,m,l,r,a[id].x);
}else{
break;
}
}
}
printf("Case #%d:",++o);
for(int i=1;i<=m;i++) printf(" %lld",qry(1,1,m,i));
cout<<endl;
}
}代码二：
方法二
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const int N=1e5+7;
struct node{int t,x;}a[N];
int T,o;
int n,m;
ll tree[4*N],tap[4*N];
int tot;
node ho[N];
bool cmp(node x,node y){
if(x.t==y.t) return x.x>y.x;
return x.t<y.t;
}
void init(int k,int l,int r){
tap[k]=-1;
if(l==r){
tree[k]=0;
return ;
}
init(lch,l,mid);
init(rch,mid+1,r);
tree[k]=max(tree[lch],tree[rch]);
}
void pushdown(int k){
if(tap[k]!=-1){
tree[lch]=max(tree[lch],tap[k]);
tree[rch]=max(tree[rch],tap[k]);
tap[lch]=max(tap[lch],tap[k]);
tap[rch]=max(tap[rch],tap[k]);
tap[k]=-1;
}
}
void update(int k,int l,int r,int ql,int qr,ll val){
if(ql<=l&&r<=qr){
//懒标空为-1,也满足取max。
tap[k]=max(tap[k],val);
tree[k]=max(tree[k],val);
return;
}
pushdown(k);
if(ql<=mid) update(lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(rch,mid+1,r,ql,qr,val);
}
ll qry(int k,int l,int r,int p){
if(l==r){
return tree[k];
}
pushdown(k);
if(p<=mid) return qry(lch,l,mid,p);
else return qry(rch,mid+1,r,p);
}
int main(){
cin>>T;
while(T--){
scanf("%d %d",&n,&m);
tot=0;
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].t,&a[i].x);
}
sort(a+1,a+1+n,cmp);
int now=-1;
for(int i=1;i<=n;i++){
if(now==a[i].t) continue;
else{
now=a[i].t;
ho[++tot]={a[i].t,a[i].x};
}
}
init(1,1,m);
for(int i=1;i<=tot;i++){
int t=ho[i].t,x=ho[i].x;
for(int k=0;;k++){
int l=2*k*t+1,r=2*k*t+t;
r=min(m,r);
if(l<=m){
update(1,1,m,l,r,x);
}else{
break;
}
}
}
printf("Case #%d:",++o);
for(int i=1;i<=m;i++) printf(" %lld",qry(1,1,m,i));
cout<<endl;
}
}区间覆盖每个点覆盖次数最大值
题意：
n条区间，选m个区间使得m个区间至少都覆盖了某个点，定义所选区间的价值为最长区间长度-最大区间长度，问所有方案中花费最小的。
思路：
题目问区间最长-区间最短的值最小。我们可以对其按区间长度排序，那么差值一定是一段连续的区间，我们观察即可发现定$l$，$r$是具有单调性的，我们即可用尺取统计答案。
添加区间的$l_i，r_i$全部$+1$，移除区间是$l_i,r_i$全部$-1$，最后查询全部区间Max是否等于$m，$为$m$时$，ans=min(ans,len_r-len_l),$我们可以知$len_r$肯定是在选的$m$里，但$len_l$不一定在选的$m$里，所以答案可能不合法，但是取$min$可将其排除。
可用到线段树进行操作。
启发：
像二分，或尺取这类具有单调性的题目有时，有时单次得到的答案区间可能并不合法，但通过其单调性还是能找到合法的答案。
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#define lch (k<<1)
#define rch ((k<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const int N=4e6+7;
struct node{int l,r,len;}a[N];
int n,m;
int tree[4*N],tap[4*N];
vector <int> ho;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int cmp(node x,node y){
return x.len<y.len;
}
inline void init(int k,int l,int r){
tap[k]=0;
if(l==r){
tree[k]=0;
return;
}
init(lch,l,mid);
init(rch,mid+1,r);
tree[k]=max(tree[lch],tree[rch]);
}
inline void pushdown(int k){
if(tap[k]){
tree[lch]=tree[lch]+tap[k];
tree[rch]=tree[rch]+tap[k];
tap[lch]=tap[lch]+tap[k];
tap[rch]=tap[rch]+tap[k];
tap[k]=0;
}
}
inline void update(int k,int l,int r,int ql,int qr,int val){
if(ql>qr) return ;
if(ql<=l&&r<=qr){
tree[k]=tree[k]+val;
tap[k]=tap[k]+val;
return;
}
pushdown(k);
if(ql<=mid) update(lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(rch,mid+1,r,ql,qr,val);
tree[k]=max(tree[lch],tree[rch]);
}
inline int query(int k,int l,int r,int ql,int qr){
if(ql>qr) return 0;
if(ql<=l&&r<=qr){
return tree[k];
}
pushdown(k);
int mx1=0,mx2=0;
if(ql<=mid) mx1=query(lch,l,mid,ql,qr);
if(mid+1<=qr) mx2=query(rch,mid+1,r,ql,qr);
return max(mx1,mx2);
}
inline int get(int x){return lower_bound(ho.begin(),ho.end(),x)-ho.begin()+1;}
int main(){
n=read(),m=read();
for(register int i=1;i<=n;i++){
a[i].l=read(),a[i].r=read();
a[i].len=a[i].r-a[i].l+1;
ho.push_back(a[i].l);
ho.push_back(a[i].r);
}
sort(a+1,a+1+n,cmp);
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
for(register int i=1;i<=n;i++){
a[i].l=lower_bound(ho.begin(),ho.end(),a[i].l)-ho.begin()+1;
a[i].r=lower_bound(ho.begin(),ho.end(),a[i].r)-ho.begin()+1;
}
int s=ho.size();
int l=1,r=0,res=1e9;
init(1,1,s);
while(l<=n){
while((r<n)&&(tree[1]<m)){
update(1,1,s,a[r+1].l,a[r+1].r,1);
r++;
}
if(tree[1]==m){
res=min(res,a[r].len-a[l].len);
}
update(1,1,s,a[l].l,a[l].r,-1);
l++;
}
if(res==1e9) printf("-1\n");
else printf("%d\n",res);
}
区间覆盖每个点覆盖次数最小值（或区间是否完全覆盖）
题意：
给你$n$个区间$l_i$,$r_i$,和价值$w_i$,选出集合S，集合的价值为最大价值-最小价值，完全覆盖区间$[1,m]$,其中线段之间连接处要相交。集合最小价值是多少。
思路：
很容易看出，如果我们对区间按$w_i$排序，那么集合一定是个连续的区间，且我们定l，r具有单调性，那么我们能用尺取统计答案。
我们要判断区间是否完全覆盖，我们用线段树维护区间覆盖次数最小值$mn$，如何$mn<0$说明有区间未覆盖到，其中区间要重叠，我们$r_i--$。
代码：
#include <iostream>
#include <algorithm>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=3e5+10,M=1e6+10;
struct node{
int l,r,w;
bool operator <(const node t)const{
return w<t.w;
}
}a[N];
int n,m,tr[4*M],lz[4*M];
void pushup(int k){
tr[k]=min(tr[lch],tr[rch]);
}
int pushdown(int k,int zl,int yl){
if(lz[k]){
tr[lch]=tr[lch]+lz[k];
tr[rch]=tr[rch]+lz[k];
lz[lch]=lz[lch]+lz[k];
lz[rch]=lz[rch]+lz[k];
lz[k]=0;
}
}
void build(int k,int l,int r){
lz[k]=0;
if(l==r){
tr[k]=0;
return;
}
build(lch,l,mid);
build(rch,mid+1,r);
pushup(k);
}
void update(int k,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
tr[k]=tr[k]+v;
lz[k]=lz[k]+v;
return;
}
pushdown(k,mid-l+1,r-mid);
if(ql<=mid) update(lch,l,mid,ql,qr,v);
if(qr>mid) update(rch,mid+1,r,ql,qr,v);
pushup(k);
}
int query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[k];
}
pushdown(k,mid-l+1,r-mid);
if(qr<=mid) return query(lch,l,mid,ql,qr);
else if(ql>mid) return query(rch,mid+1,r,ql,qr);
else return query(lch,l,mid,ql,qr)+query(rch,mid+1,r,ql,qr);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r>>a[i].w;
}
sort(a+1,a+1+n);
build(1,1,m);
int idx=0,ans=1e9;
for(int i=1;i<=n;i++){
while(idx+1<=n&&tr[1]<=0) update(1,1,m,a[idx+1].l,(a[idx+1].r==m)?m:a[idx+1].r-1,1),idx++;
if(tr[1]>0) ans=min(ans,a[idx].w-a[i].w);
update(1,1,m,a[i].l,(a[i].r==m)?m:a[i].r-1,-1);
}
cout<<ans<<"\n";
}线段树常用二分
前言：
线段树二分各式各样，一般如果区间满足一定的单调性，我们可以考虑用在线段树上继续二分，下面总结下一些常用的二分及其写法。
区间第k大的数(代替set)
题意：
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入 xx 数
- 删除 xx 数(若有多个相同的数，因只删除一个)
- 查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )
- 查询排名为 xx 的数
- 求 xx 的前驱(前驱定义为小于 xx，且最大的数)
- 求 xx 的后继(后继定义为大于 xx，且最小的数)
思路：
线段树上二分，和离散化能够完美解决。
代码：
#include <iostream>
#include <vector>
#include <algorithm>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int N=1e6+10;
int n;
struct Q{
int op,x;
}q[N];
int tr[4*N];
vector <int> ho;
int get(int x){
return lower_bound(ho.begin(),ho.end(),x)-ho.begin()+1;
}
void insert(int k,int l,int r,int p,int v){
tr[k]=max(0,tr[k]+v);
if(l==r) return;
if(p<=mid) insert(lch,l,mid,p,v);
else insert(rch,mid+1,r,p,v);
}
int query(int k,int l,int r,int ql,int qr){
if(ql>qr) return 0;
if(ql<=l&&r<=qr){
return tr[k];
}
if(qr<=mid) return query(lch,l,mid,ql,qr);
else if(ql>mid) return query(rch,mid+1,r,ql,qr);
else return query(lch,l,mid,ql,qr)+query(rch,mid+1,r,ql,qr);
}
int ask(int k,int l,int r,int key){
if(l==r){
return l;
}
int tem=tr[lch];
if(key<=tem) return ask(lch,l,mid,key);
else return ask(rch,mid+1,r,key-tem);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>q[i].op>>q[i].x;
if(q[i].op!=4) ho.push_back(q[i].x);
}
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
for(int i=1;i<=n;i++){
if(q[i].op!=4) q[i].x=get(q[i].x);
}
for(int i=1;i<=n;i++){
if(q[i].op==1){
insert(1,1,n,q[i].x,1);
}else if(q[i].op==2){
insert(1,1,n,q[i].x,-1);
}else if(q[i].op==3){
cout<<query(1,1,n,1,q[i].x-1)+1<<"\n";
}else if(q[i].op==4){
cout<<ho[ask(1,1,n,q[i].x)-1]<<"\n";
}else if(q[i].op==5){
int k=query(1,1,n,1,q[i].x-1);
cout<<ho[ask(1,1,n,k)-1]<<"\n";
}else{
int k=query(1,1,n,1,q[i].x)+1;
cout<<ho[ask(1,1,n,k)-1]<<"\n";
}
}
}
查询区间右端开始最近大于x的位置（即前缀MAX）
题意：
给你n个任务，每个任务都有结束时间。
查询01串区间右端开始最长0位置。
题意：
给你$n\times m$的矩阵，$k$个位置$(x_i,y_j)$有陷阱，问从(1,1)能到达哪些点。
思路：
将陷阱按照每一行压入vector里面，然后一行一行判断，每行的陷阱将区间分割为若干块[l,r]，即这些块的僵尸只能从上一行区间[l,r]中转移过来，在上行[l,r]中，我们需要算出其僵尸最左端出现的位置x，即当前行区间[x,r]僵尸都可达。
要得到区间[l,r]僵尸最左端,我们能用线段树维护，令0为僵尸不能达的位置，1为僵尸可达的位置，那么即算出区间[l,r]中左端最长连续0的位置，即我们可以用线段树二分实现。（貌似维护连续信息之间维护）。ps：这里当前行与上一行要用到两棵线段树。
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#define lch (k<<1)
#define rch (k<<1|1)
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=1e5+7;
const int inf=1e9;
int T;
int n,m,k,tree[2][4*N],tap[2][4*N];
vector <int> ho[N];
void init(int f,int k,int l,int r){
tap[f][k]=-1;
if(l==r){
tree[f][k]=0;
return;
}
init(f,lch,l,mid);
init(f,rch,mid+1,r);
tree[f][k]=tree[f][lch]+tree[f][rch];
}
void pushdown(int f,int k,int zl,int yl){
if(tap[f][k]!=-1){
tree[f][lch]=tap[f][k]*(zl);
tree[f][rch]=tap[f][k]*(yl);
tap[f][lch]=tap[f][k];
tap[f][rch]=tap[f][k];
tap[f][k]=-1;
}
}
void update(int f,int k,int l,int r,int ql,int qr,int val){
if(ql>qr) return;
if(ql<=l&&r<=qr){
tree[f][k]=val*(r-l+1);
tap[f][k]=val;
return;
}
pushdown(f,k,mid-l+1,r-mid);
if(ql<=mid) update(f,lch,l,mid,ql,qr,val);
if(mid+1<=qr) update(f,rch,mid+1,r,ql,qr,val);
tree[f][k]=tree[f][lch]+tree[f][rch];
}
ll query(int f,int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tree[f][k];
}
pushdown(f,k,mid-l+1,r-mid);
ll sum1=0,sum2=0;
if(ql<=mid) sum1=query(f,lch,l,mid,ql,qr);
if(mid+1<=qr) sum2=query(f,rch,mid+1,r,ql,qr);
return sum1+sum2;
}
int work(int f,int k,int l,int r,int ql,int qr){
if(!tree[f][k]) return inf;
if(l==r) return l;
pushdown(f,k,mid-l+1,r-mid);
if(ql<=l&&r<=qr){
if(tree[f][lch]>0) return work(f,lch,l,mid,l,mid);
else return work(f,rch,mid+1,r,mid+1,r);
}
int id=inf;
if(ql<=mid) id=min(id,work(f,lch,l,mid,ql,qr));
if(mid+1<= qr) id=min(id,work(f,rch,mid+1,r,ql,qr));
return id;
}
void gao(int p){
int l=0;
for(int i=0;i<ho[p].size();i++){
int ed=ho[p][i];
if(l+1<=ed-1){
int pos=work((p&1)^1,1,1,m,l+1,ed-1);
if(pos!=inf) update((p&1),1,1,m,pos,ed-1,1);
}
l=ed;
}
if(l+1<=m){
int pos=work((p&1)^1,1,1,m,l+1,m);
if(pos!=inf) update((p&1),1,1,m,pos,m,1);
}
update((p&1)^1,1,1,m,1,m,0);
}
void solve(){
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++) ho[i].clear();
for(int i=1;i<=k;i++){
int x,y;
scanf("%d %d",&x,&y);
ho[x].push_back(y);
}
init(0,1,1,m);init(1,1,1,m);
for(int i=1;i<=n;i++){
sort(ho[i].begin(),ho[i].end());
}
ll ans=0;
update(0,1,1,m,1,1,1);
for(int i=1;i<=n;i++){
gao(i);
ans+=query(i&1,1,1,m,1,m);
}
printf("%lld\n",ans);
}
int main(){
scanf("%d",&T);
while(T--) solve();
}主席树
前言：
主席树是带历史版本的线段树，最常用的是按前缀建主席树，使其有前缀和的性质，在树上又能够按dfs序建，即可维护子树信息，也可以按深度建树，主席树用法很灵活，由于建多课线段树，类是将按根节点分类，根据根节点限制，又能根据区间限制，两个限制。
区间第k大
题意：
给你个序列，求区间$l,r$的第$k$小的数
思路:
我们建按前缀建主席树，即主席树具有前缀和的性质，更具前缀和相减即可维护[l,r]区间的权值，然后二分。
代码：
#include <iostream>
#include <vector>
#include <algorithm>
#define mid (l+r>>1)
using namespace std;
const int N=1e5+7;
struct node{int lc,rc,v;}tr[40*N];
int n,m,tot,a[N],rt[N];
vector <int> ho;
void insert(int &k,int pr,int l,int r,int p){
k=++tot,tr[k]=tr[pr],tr[k].v++;
if(l==r) return;
if(p<=mid) insert(tr[k].lc,tr[pr].lc,l,mid,p);
else insert(tr[k].rc,tr[pr].rc,mid+1,r,p);
}
int ask(int k,int pr,int l,int r,int key){
if(l==r) return l;
int tem=tr[tr[k].lc].v-tr[tr[pr].lc].v;
if(tem>=key) return ask(tr[k].lc,tr[pr].lc,l,mid,key);
else return ask(tr[k].rc,tr[pr].rc,mid+1,r,key-tem);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ho.push_back(a[i]);
}
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
for(int i=1;i<=n;i++){
a[i]=lower_bound(ho.begin(),ho.end(),a[i])-ho.begin()+1;
insert(rt[i],rt[i-1],1,n,a[i]);
}
while(m--){
int l,r,k;
scanf("%d %d %d",&l,&r,&k);
int id=ask(rt[r],rt[l-1],1,n,k);
printf("%d\n",ho[id-1]);
}
}主席树区间修改
题意：
给你一串序列，每次对它有四种操作，
1.C l r d:将l到r之间所有的数+d，同时时间戳+1。
2.Q l r:查询当前时间戳下l到r的所有数的总和。
3.H l r t:.查询时间戳t下的l到r的所有数的和。
4.B t:将时间戳返回至t。
思路：
标准线段树操作，但里面具有区间修改，我们区间修改时可以标记懒标记但是不下传，因为下传会破坏树的结构，然后查询时将懒标记加上。
代码：
#include <iostream>
#include <cstring>
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=1e5+10,M=1e5+10;
struct node{
int lc,rc;
ll v,lz;
}tr[40*N];
ll a[N];
int n,m,tot,rt[40*M];
void init(){
for(int i=0;i<=tot;i++) tr[i].lc=tr[i].rc=tr[i].v=tr[i].lz=0;
for(int i=0;i<=m;i++) rt[i]=0;
tot=0;
}
void build(int &k,int l,int r){
k=++tot;
tr[k].v=a[l];
tr[k].lz=0;
if(l==r){
tr[k].v=a[l];
return;
}
build(tr[k].lc,l,mid);
build(tr[k].rc,mid+1,r);
tr[k].v=tr[tr[k].lc].v+tr[tr[k].rc].v;
}
void insert(int &k,int pr,int l,int r,int ql,int qr,ll v){
k=++tot;
tr[k]=tr[pr];tr[k].v+=1ll*(qr-ql+1)*v;
if(ql<=l&&r<=qr){
tr[k].lz+=v;
return;
}
if(qr<=mid)
insert(tr[k].lc,tr[pr].lc,l,mid,ql,qr,v);
else if(ql>mid)
insert(tr[k].rc,tr[pr].rc,mid+1,r,ql,qr,v);
else{
insert(tr[k].lc,tr[pr].lc,l,mid,ql,mid,v);
insert(tr[k].rc,tr[pr].rc,mid+1,r,mid+1,qr,v);
}
}
ll query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[k].v;
}
ll ans=1ll*tr[k].lz*(qr-ql+1);
if(qr<=mid) return ans+query(tr[k].lc,l,mid,ql,qr);
else if(ql>mid) return ans+query(tr[k].rc,mid+1,r,ql,qr);
else return ans+query(tr[k].lc,l,mid,ql,mid)+query(tr[k].rc,mid+1,r,mid+1,qr);
}
void solve(){
init();
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(rt[0],1,n);
int tim=0;
while(m--){
char op[2];
int l,r,d,t;
scanf("%s",op);
if(*op=='C'){
scanf("%d %d %d",&l,&r,&d);
insert(rt[tim+1],rt[tim],1,n,l,r,d);
tim++;
}else if(*op=='Q'){
scanf("%d %d",&l,&r);
printf("%lld\n",query(rt[tim],1,n,l,r));
}else if(*op=='H'){
scanf("%d %d %d",&l,&r,&t);
printf("%lld\n",query(rt[t],1,n,l,r));
}else{
scanf("%d",&t);
tim=t;
}
}
}
int main(){
while(scanf("%d %d",&n,&m)!=EOF) solve();
}按父亲建主席树(树上路径第k小)
题意：
给定一棵 $n$ 个节点的树，每个点有一个权值。有 $m$个询问，每次给你 $u,v,k$，你需要回答 $u$ 和 $v$这两个节点间第 $k$ 小的点权。
思路：
我们可以按父亲建主席树，然后每棵主席树维护其该节点到根的权值，我们可以求出两点的LCA，然后通过加减即可得到节点$u,v$的权值，然后二分。
代码：
#include <iostream>
#include <algorithm>
#include <vector>
#define mid ((l+r)>>1)
using namespace std;
const int N=2e5+7;
struct node{int to,next;}e[N];
struct Tree{int lch,rch,sum;}tree[40*N];
int n,m,QAQ,idx;
int a[N],root[N];
int head[N],tot;
vector <int> ho;
void add(int u,int v){
e[++tot].to=v;
e[tot].next=head[u];
head[u]=tot;
}
int get_key(int x){return lower_bound(ho.begin(),ho.end(),x)-ho.begin()+1;}
void insert(int pre,int &now ,int l,int r,int p){
tree[++idx]=tree[pre],now=idx,tree[now].sum++;
if(l>=r) return;
if(p<=mid) insert(tree[pre].lch,tree[now].lch,l,mid,p);
else insert(tree[pre].rch,tree[now].rch,mid+1,r,p);
}
int dfs(int p,int fa){
insert(root[fa],root[p],1,n,a[p]);
for(int i=head[p];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
dfs(v,p);
}
}
int father[N][30],lg[N],deep[N];
void ddfs(int u,int fa){
father[u][0]=fa;
deep[u]=deep[fa]+1;
for(int i=1;(1<<i)<deep[u];i++){
father[u][i]=father[father[u][i-1]][i-1];
}
for(int i=head[u];i!=0;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
ddfs(v,u);
}
}
int LCA(int x,int y){
if(deep[x]<deep[y]) swap(x,y);
while(deep[x]>deep[y]){
x=father[x][lg[deep[x]-deep[y]]-1];
}
if(x==y) return x;
for(int k=lg[deep[x]]-1;k>=0;k--){
if(father[x][k]!=father[y][k]){
x=father[x][k],y=father[y][k];
}
}
return father[x][0];
}
int qry(int U,int V,int M1,int M2,int l,int r,int key){
if(l>=r) return l;
int tem=tree[tree[U].lch].sum+tree[tree[V].lch].sum-tree[tree[M1].lch].sum-tree[tree[M2].lch].sum;
if(key<=tem) return qry(tree[U].lch,tree[V].lch,tree[M1].lch,tree[M2].lch,l,mid,key);
else return qry(tree[U].rch,tree[V].rch,tree[M1].rch,tree[M2].rch,mid+1,r,key-tem);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
ho.push_back(a[i]);
}
sort(ho.begin(),ho.end());
ho.erase(unique(ho.begin(),ho.end()),ho.end());
for(int i=1;i<=n;i++){
a[i]=get_key(a[i]);
}
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}
dfs(1,0);
ddfs(1,0);
while(m--){
int u,v,k;
scanf("%d %d %d",&u,&v,&k);
int lca=LCA(u^QAQ,v);
QAQ=ho[qry(root[u^QAQ],root[v],root[lca],root[father[lca][0]],1,n,k)-1];
printf("%d\n",QAQ);
}
}按dfs序建主席树（维护子树）
题意：
给定一个树形结构,每个节点有个温度$t_i$,$1$号点是树根.越接近树根温度越高,现有一种生存温度在$[L,R]$区间病毒在点X处出现,如果某个节点的温度在$[L,R]$区间,且与其相邻的点感染了病毒,那么这个点也会感染病毒
有很多询问,每次询问在$X$点爆发一种生存温度[L,R]的病毒,最多能感染多少个点
思路：
由于温度有单调性，如果父亲节点被感染，即父亲节也在[L,R]里，我们可以通过倍增找到被感染的祖先，即R的上届，然后要查询其子树在$[L,R]$里面，我们用主席树按dfs序建树即可。
代码：
#include <iostream>
#define mid (l+r>>1)
using namespace std;
const int N=1e5+7;
const int S=1e9;
struct NODE {int lch,rch,v;}tr[160*N];
struct node {int to,next;}e[2*N];
int T;
int n,m,sz[N],root[N],t[N],dfn[N],f[N][21];
int head[N],tot,tim;
void insert(int& rt,int pr,int l,int r,int p){
rt=++tot,tr[rt]=tr[pr],tr[rt].v++;
if(l==r) return;
if(p<=mid) insert(tr[rt].lch,tr[pr].lch,l,mid,p);
else insert(tr[rt].rch,tr[pr].rch,mid+1,r,p);
}
int ask(int k,int l,int r,int p){
if(l==r) return tr[k].v;
if(p<=mid) return ask(tr[k].lch,l,mid,p);
else return ask(tr[k].rch,mid+1,r,p);
}
int query(int L,int R,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tr[R].v-tr[L].v;
if(qr<=mid) return query(tr[L].lch,tr[R].lch,l,mid,ql,qr);
else if(ql>mid) return query(tr[L].rch,tr[R].rch,mid+1,r,ql,qr);
else return query(tr[L].lch,tr[R].lch,l,mid,ql,qr)+query(tr[L].rch,tr[R].rch,mid+1,r,ql,qr);
}
void add(int u,int v){
e[++tot].to=v;
e[tot].next=head[u];
head[u]=tot;
}
void ikuzo(int p,int fa){
f[p][0]=fa;dfn[p]=++tim;sz[p]=1;
insert(root[dfn[p]],root[dfn[p]-1],1,S,t[p]);
for(int i=head[p];i;i=e[i].next){
int v=e[i].to;
if(v==fa) continue;
ikuzo(v,p);
sz[p]+=sz[v];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d %d",&u,&v);
add(u,v);add(v,u);
}
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
}
ikuzo(1,1);
f[0][0]=0;
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
f[j][i]=f[f[j][i-1]][i-1];
}
}
scanf("%d",&m);
while(m--){
int x,l,r;
scanf("%d %d %d",&x,&l,&r);
if(t[x]>r||t[x]<l){puts("0");continue;}
int p=x;
for(int i=19;i>=0;i--){
if(t[f[p][i]]<=r) p=f[p][i];
}
printf("%d\n",query(root[dfn[p]-1],root[dfn[p]+sz[p]-1],1,S,l,r));
}
}按深度建主席树
题意：
给你一颗有根树，点有权值，$m$ 次询问，每次问你某个点的子树中距离其不超过 $k$ 的点的权值的最小值。（边权均为 $1$，点权有可能重复，$k$值每次询问有可能不同）
思路：
一般询问子树问题都用dfs序，建主席树，但这题询问min，不能进行区间加减，我们换一种想法，按深度建树，然后查询dfs序的范围查询$min$
总结：
主席树的桉树分类，和其值域区间类似有两种限制，按什么主席树建主席树的方式各种各样，有时值域和建树能够换过来建。
代码
#include <iostream>
#include <algorithm>
#include <vector>
#define mid (l+r>>1)
using namespace std;
const int N=1e5+10,S=1e5;
const int inf=1e9;
struct node{
int lc,rc,v;
}tr[40*N];
int n,m,tot,tim,root;
int dfn[N],a[N],rt[N],sz[N],dep[N];
vector <int> G[N],orn;
bool cmp(int x,int y){
return dep[x]<dep[y];
}
void build(int &k,int l,int r){
k=++tot;
if(l==r){
tr[k].v=inf;
return;
}
build(tr[k].lc,l,mid);
build(tr[k].rc,mid+1,r);
tr[k].v=min(tr[tr[k].lc].v,tr[tr[k].rc].v);
}
void insert(int &k,int pre,int l,int r,int p,int v){
k=++tot,tr[k]=tr[pre];
if(l==r){
tr[k].v=min(v,tr[k].v);
return;
}
if(p<=mid) insert(tr[k].lc,tr[pre].lc,l,mid,p,v);
else insert(tr[k].rc,tr[pre].rc,mid+1,r,p,v);
tr[k].v=min(tr[tr[k].lc].v,tr[tr[k].rc].v);
}
int query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[k].v;
}
if(qr<=mid) return query(tr[k].lc,l,mid,ql,qr);
else if(ql>mid) return query(tr[k].rc,mid+1,r,ql,qr);
else return min(query(tr[k].lc,l,mid,ql,qr),query(tr[k].rc,mid+1,r,ql,qr));
}
void dfs(int p,int fa,int deep){
dfn[p]=++tim;dep[p]=deep;
sz[p]=1;
for(auto v:G[p]){
if(v==fa) continue;
dfs(v,p,deep+1);
sz[p]+=sz[v];
}
}
int main(){
scanf("%d %d",&n,&root);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
build(rt[0],1,S);
dfs(root,0,1);
for(int i=0;i<=n;i++) orn.push_back(i);
sort(orn.begin(),orn.end(),cmp);
for(int i=1;i<orn.size();i++){
insert(rt[dep[orn[i]]],rt[dep[orn[i-1]]],1,S,dfn[orn[i]],a[orn[i]]);
}
scanf("%d",&m);
int ans=0;
while(m--){
int p,q,x,k;
scanf("%d %d",&p,&q);
x=(p+ans)%n+1,k=(q+ans)%n;
ans=query(rt[min(dep[orn[n]],dep[x]+k)],1,S,dfn[x],dfn[x]+sz[x]-1);
printf("%d\n",ans);
}
}
线段树合并和分裂
线段树合并
题意：
给出一个有n个节点的树, 有m次操作a b c表示给节点a, b所在的路径上增加1个c颜色.
最后对于每个节点询问, 求当前节点最多的颜色是哪种.
思路：
我们如果对于每个路径修改进行差分，那么最后统计的就是答案，但这里问的是种类，我们需要维护每个点的值域，这样需要多个线段树，而且需要合并，但刚好动态开点线段树支持这种操作，而且总共的均摊的复杂度是$O(nlogn)$
代码:
#include <iostream>
#include <vector>
#define mid (l+r>>1)
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pll;
const int N=1e5+10,S=1e5;
int n,m,tot,Ans[N];
int rt[N],fa[N],son[N],dep[N],sz[N],top[N];
vector <int> G[N];
struct node{
int lc,rc;
pll s;
}tr[70*N];
void ikuzo(int p,int faz){
fa[p]=faz,sz[p]=1;
dep[p]=dep[faz]+1;
for(auto v:G[p]){
if(v==faz) continue;
ikuzo(v,p);
sz[p]+=sz[v];
if(sz[son[p]]<sz[v]){
son[p]=v;
}
}
}
void dfs(int p,int t){
top[p]=t;
if(son[p]) dfs(son[p],t);
for(auto v:G[p]){
if(v==fa[p]||son[p]==v) continue;
dfs(v,v);
}
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]? x:y;
}
pll max(pll x,pll y){
if(x.fi>y.fi) return x;
else if(x.fi<y.fi) return y;
else{
if(x.se<y.se) return x;
else return y;
}
}
void pushup(int k){
tr[k].s=max(tr[tr[k].lc].s,tr[tr[k].rc].s);
}
void modify(int &k,int l,int r,int p,int v){
if(!k) k=++tot;
if(l==r){
tr[k].s=pll(tr[k].s.fi+v,l);
return;
}
if(p<=mid) modify(tr[k].lc,l,mid,p,v);
else modify(tr[k].rc,mid+1,r,p,v);
pushup(k);
}
//线段树合并
void merge(int &L,int R,int l,int r){
if(!L||!R){
L|=R;
}else if(l==r){
tr[L].s.fi+=tr[R].s.fi;
}else{
merge(tr[L].lc,tr[R].lc,l,mid);
merge(tr[L].rc,tr[R].rc,mid+1,r);
pushup(L);
}
}
void gao(int p){
for(auto v:G[p]){
if(v==fa[p]) continue;
gao(v);
merge(rt[p],rt[v],1,S);
}
if(rt[p]) Ans[p]=tr[rt[p]].s.se;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
ikuzo(1,0);
dfs(1,1);
while(m--){
int x,y,z;
cin>>x>>y>>z;
int t=lca(x,y);
//进行树上差分
modify(rt[x],1,S,z,1);
modify(rt[y],1,S,z,1);
modify(rt[t],1,S,z,-1);
modify(rt[fa[t]],1,S,z,-1);
}
gao(1);
for(int i=1;i<=n;i++) cout<<Ans[i]<<"\n";
}
线段树分裂
题目：
给出一个可重集 $a$（编号为$ 1$），它支持以下操作：
0 p x y：将可重集 $p$ 中大于等于 $x$ 且小于等于 $y$ 的值放入一个新的可重集中（新可重集编号为从 $2$ 开始的正整数，是上一次产生的新可重集的编号$+1$）。
1 p t：将可重集$ t$ 中的数放入可重集 $p$，且清空可重集$ t$（数据保证在此后的操作中不会出现可重集 t）。
2 p x q：在 $p$ 这个可重集中加入$ x$ 个数字 $q$。
3 p x y：查询可重集 $p$ 中大于等于 x 且小于等于 $y$ 的值的个数。
4 p k：查询在 $p$ 这个可重集中第 $k$ 小的数，不存在时输出 -1。
思路：
就是线段树合并和分裂板子
代码：
#include <iostream>
#define mid (l+r>>1)
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct node{
int lc,rc;
ll v;
}tr[80*N];
int n,m,tot;
int a[N],rt[N];
int pushup(int k){
tr[k].v=tr[tr[k].lc].v+tr[tr[k].rc].v;
}
int split(int &k,int l,int r,int ql,int qr){
int orn=++tot;
if(ql<=l&&r<=qr){
tr[orn]=tr[k];
k=0;
}else{
if(ql<=mid) tr[orn].lc=split(tr[k].lc,l,mid,ql,qr);
if(qr>mid) tr[orn].rc=split(tr[k].rc,mid+1,r,ql,qr);
pushup(orn),pushup(k);
}
return orn;
}
void merge(int &L,int R){
if(!L||!R) L|=R;
else{
tr[L].v+=tr[R].v;
merge(tr[L].lc,tr[R].lc);
merge(tr[L].rc,tr[R].rc);
}
}
ll query(int k,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[k].v;
}
if(qr<=mid) return query(tr[k].lc,l,mid,ql,qr);
else if(ql>mid) return query(tr[k].rc,mid+1,r,ql,qr);
else return query(tr[k].lc,l,mid,ql,qr)+query(tr[k].rc,mid+1,r,ql,qr);
}
ll ask(int k,int l,int r,int key){
if(l==r){
if(key>tr[k].v) return -1;
return l;
}
ll tem=tr[tr[k].lc].v;
if(tem>=key) return ask(tr[k].lc,l,mid,key);
else return ask(tr[k].rc,mid+1,r,key-tem);
}
void insert(int &k,int l,int r,int p,int v){
if(!k) k=++tot;
tr[k].v+=v;
if(l==r) return;
if(p<=mid) insert(tr[k].lc,l,mid,p,v);
else insert(tr[k].rc,mid+1,r,p,v);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],insert(rt[1],1,n,i,a[i]);
int now=1;
while(m--){
int op,p,x,y,t,q,k;
cin>>op;
if(op==0){
cin>>p>>x>>y;
rt[++now]=split(rt[p],1,n,x,y);
}else if(op==1){
cin>>p>>t;
merge(rt[p],rt[t]);
}else if(op==2){
cin>>p>>x>>q;
insert(rt[p],1,n,q,x);
}else if(op==3){
cin>>p>>x>>y;
cout<<query(rt[p],1,n,x,y)<<"\n";
}else{
cin>>p>>k;
if(k<=tr[rt[p]].v) cout<<ask(rt[p],1,n,k)<<"\n";
else cout<<"-1\n";
}
}
}
此处评论已关闭