【做題記錄】線段樹（馬思博）
SP1043 GSS1 - Can you answer these queries I
貓樹——線性對數預處理，常數查詢的優秀數據結構。
其實它是線段樹的一個變種。考慮線段樹的每個節點 \([L,R]\)，對于 \(i\in[L,mid]\) 維護 \([i,mid]\) 的信息，對于 \(i\in[mid+1,R]\) 維護 \([mid+1,i]\) 的信息。于是對于查詢 \([l,r]\)，我們只需要找到包含這個區間的最小的節點即可 \(O(1)\) 查詢。問題變為如何快速求出這個節點，不難發現它就是 \([l,l]\) 和 \([r,r]\) 的 LCA。我們還可以發現，線段樹上同一層的兩個節點 \(x\) 和 \(y\) 的 LCA 即為它們二進制下的最長公共前綴，也就是 \(x\operatorname{rsh}(\log(x\oplus y)+1)\)。于是我們把 \(n\) 補全成最小的 \(2^k\)，使所有葉子節點都在同一層即可。具體實現時我們不考慮 LCA 的編號，只需求出它在哪一層。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=7e4+5;
int n,m,a[maxn],Log[maxn];
struct node{
int sum,mm,lm,rm;
node(int sum,int mm,int lm,int rm)
:sum(sum),mm(mm),lm(lm),rm(rm){}
node(int x=0):sum(x),mm(x),lm(x),rm(x){}
il node operator+(const node &x)const{
return node(sum+x.sum,max({mm,x.mm,rm+x.lm}),max(lm,sum+x.lm),max(x.rm,x.sum+rm));
}
}tr[17][maxn];
il void build(int l,int r,int d){
if(l==r){
tr[d][l]=node(a[l]);
return ;
}
int mid=(l+r)>>1;
tr[d][mid]=node(a[mid]);
for(int i=mid-1;i>=l;i--){
tr[d][i]=node(a[i])+tr[d][i+1];
}
tr[d][mid+1]=node(a[mid+1]);
for(int i=mid+2;i<=r;i++){
tr[d][i]=tr[d][i-1]+node(a[i]);
}
build(l,mid,d+1);
build(mid+1,r,d+1);
}
il int solve(int l,int r){
if(l==r){
return a[l];
}
int d=15-Log[(65535+l)^(65535+r)];
return (tr[d][l]+tr[d][r]).mm;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
n=65536;
for(int i=2;i<=n;i++){
Log[i]=Log[i>>1]+1;
}
build(1,n,0);
cin>>m;
while(m--){
int l,r;
cin>>l>>r;
cout<<solve(l,r)<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
G. 好吃的題目
將詢問離線下來，不建出貓樹，在遞歸過程中處理詢問，即為貓樹分治。
對于此題，考慮當前所有詢問區間的 \([l_i,r_i]\subseteq[L,R]\)，求出 \(mid=\lfloor\frac{L+R}{2}\rfloor\)，對于 \(i\in[L,mid]\) 背包 DP 出 \(f_{i,j}\) 表示 \([i,mid]\) 中 \(\le j\) 的熱量的最大美味度，對于 \(i\in[mid+1,R]\) 求出 \([mid+1,i]\) 對應的答案。對于 \(l_i\in[L,mid]\land r_i\in[mid+1,R]\) 直接 \(O(t_i)\) 計算答案，對于其他詢問遞歸處理即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=4e4+5,maxm=2e5+5;
int n,m,cnt,a[maxn];
ll b[maxn],ans[maxm],f[maxn][205];
struct{
int l,r,v,id;
}q[maxm],hp[maxm];
il void solve(int L,int R,int l,int r){
if(l>r){
return ;
}
int mid=(L+R)>>1;
for(int i=0;i<=200;i++){
f[mid][i]=(i>=a[mid])*b[mid];
f[mid+1][i]=(i>=a[mid+1])*b[mid+1];
}
for(int i=mid-1;i>=L;i--){
for(int j=0;j<=200;j++){
f[i][j]=f[i+1][j];
if(j>=a[i]){
f[i][j]=max(f[i][j],f[i+1][j-a[i]]+b[i]);
}
}
}
for(int i=mid+2;i<=R;i++){
for(int j=0;j<=200;j++){
f[i][j]=f[i-1][j];
if(j>=a[i]){
f[i][j]=max(f[i][j],f[i-1][j-a[i]]+b[i]);
}
}
}
int pl=l,pr=r;
for(int i=l;i<=r;i++){
if(q[i].l<=mid&&q[i].r>mid){
for(int j=0;j<=q[i].v;j++){
ans[q[i].id]=max(ans[q[i].id],f[q[i].l][j]+f[q[i].r][q[i].v-j]);
}
}
else if(q[i].r<=mid){
hp[pl++]=q[i];
}
else{
hp[pr--]=q[i];
}
}
for(int i=l;i<=r;i++){
q[i]=hp[i];
}
solve(L,mid,l,pl-1);
solve(mid+1,R,pr+1,r);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
}
for(int i=1,l,r,v;i<=m;i++){
cin>>l>>r>>v;
if(l==r){
if(v>=a[l]){
ans[i]=b[l];
}
}
else{
q[++cnt]={l,r,v,i};
}
}
solve(1,n,1,cnt);
for(int i=1;i<=m;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
}
int main(){return asbt::main();}
uoj228 基礎數據結構練習題
考慮兩種操作對區間極差的影響：加法操作后極差不變，開根操作后極差變小。使用線段樹，考慮較難維護的開根操作，如果這個區間極差為 \(0\) 那么可以直接轉化為加法操作，否則我們直接暴力遞歸左右子區間。考慮時間復雜度，發現每個區間經過至多 \(5\) 次開根操作后極差就會變為 \(0\)，因此是正確的。
然而有一個特殊情況可以把這個算法卡爆，那就是開根后極差不變。容易證明這只有一個情況，那就是 \(k^2-1\) 和 \(k^2\)。發現此時開根后它們的變化量也是一樣的，于是特判掉即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m;
ll a[maxn],sum[maxn<<2],mx[maxn<<2],mn[maxn<<2],tag[maxn<<2];
il void pushup(int id){
sum[id]=sum[lid]+sum[rid];
mx[id]=max(mx[lid],mx[rid]);
mn[id]=min(mn[lid],mn[rid]);
}
il void pushtag(int id,int l,int r,ll v){
sum[id]+=(r-l+1)*v;
mx[id]+=v,mn[id]+=v,tag[id]+=v;
}
il void pushdown(int id,int l,int r){
if(tag[id]){
int mid=(l+r)>>1;
pushtag(lid,l,mid,tag[id]);
pushtag(rid,mid+1,r,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r){
if(l==r){
sum[id]=mx[id]=mn[id]=a[l];
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void add(int id,int L,int R,int l,int r,ll v){
if(L>=l&&R<=r){
pushtag(id,L,R,v);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
add(lid,L,mid,l,r,v);
}
if(r>mid){
add(rid,mid+1,R,l,r,v);
}
pushup(id);
}
il void pfg(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
ll sq=sqrt(mx[id]);
if(mx[id]==mn[id]||mx[id]-mn[id]==1&&sq*sq==mx[id]){
pushtag(id,L,R,sq-mx[id]);
return ;
}
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
pfg(lid,L,mid,l,r);
}
if(r>mid){
pfg(rid,mid+1,R,l,r);
}
pushup(id);
}
il ll query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return sum[id];
}
pushdown(id,L,R);
int mid=(L+R)>>1;
ll res=0;
if(l<=mid){
res+=query(lid,L,mid,l,r);
}
if(r>mid){
res+=query(rid,mid+1,R,l,r);
}
return res;
}
//il void debug(int id,int l,int r){
// cout<<l<<" "<<r<<" "<<sum[id]<<" "<<mx[id]<<" "<<mn[id]<<" "<<tag[id]<<"\n";
// if(l==r){
// return ;
// }
// pushdown(id,l,r);
// int mid=(l+r)>>1;
// debug(lid,l,mid);
// debug(rid,mid+1,r);
//}
int main(){
// system("fc ex_data2.out my.out");
// freopen("ex_data2.in","r",stdin);
// freopen("my.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
// debug(1,1,n);
while(m--){
int opt,l,r;
cin>>opt>>l>>r;
switch(opt){
case 1:{
ll x;
cin>>x;
add(1,1,n,l,r,x);
break;
}
case 2:{
pfg(1,1,n,l,r);
break;
}
default:{
cout<<query(1,1,n,l,r)<<"\n";
break;
}
}
// debug(1,1,n);
}
return 0;
}
}
int main(){return asbt::main();}
O. [TJOI2016 & HEOI2016] 排序
考慮二分答案，將 \(\ge mid\) 的設為 \(1\)，\(<mid\) 的設為 \(-1\)，于是區間排序操作就轉化為了區間查詢+推平操作，線段樹維護即可。時間復雜度線性對數方。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,q,a[maxn],cnt[maxn<<2],tag[maxn<<2];
struct{
int opt,l,r;
}b[maxn];
il void pushup(int id){
cnt[id]=cnt[lid]+cnt[rid];
}
il void pushtag(int id,int l,int r,int x){
tag[id]=x;
cnt[id]=x==1?r-l+1:0;
}
il void pushdown(int id,int l,int r){
if(tag[id]){
int mid=(l+r)>>1;
pushtag(lid,l,mid,tag[id]);
pushtag(rid,mid+1,r,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r,int x){
tag[id]=0;
if(l==r){
pushtag(id,l,r,a[l]>=x?1:-1);
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid,x);
build(rid,mid+1,r,x);
pushup(id);
}
il void upd(int id,int L,int R,int l,int r,int x){
if(l>r){
return ;
}
if(L>=l&&R<=r){
pushtag(id,L,R,x);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,x);
}
if(r>mid){
upd(rid,mid+1,R,l,r,x);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return cnt[id];
}
pushdown(id,L,R);
int mid=(L+R)>>1,res=0;
if(l<=mid){
res+=query(lid,L,mid,l,r);
}
if(r>mid){
res+=query(rid,mid+1,R,l,r);
}
return res;
}
il bool check(int x){
build(1,1,n,x);
for(int i=1,opt,l,r;i<=m;i++){
opt=b[i].opt,l=b[i].l,r=b[i].r;
int cnt=query(1,1,n,l,r);
if(opt){
upd(1,1,n,l,l+cnt-1,1);
upd(1,1,n,l+cnt,r,-1);
}
else{
upd(1,1,n,r-cnt+1,r,1);
upd(1,1,n,l,r-cnt,-1);
}
}
return query(1,1,n,q,q)==1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1,opt,l,r;i<=m;i++){
cin>>opt>>l>>r;
b[i]={opt,l,r};
}
cin>>q;
int l=1,r=n;
while(l<r){
int mid=(l+r+1)>>1;
if(check(mid)){
l=mid;
}
else{
r=mid-1;
}
}
cout<<l;
return 0;
}
}
int main(){return asbt::main();}
P. [WC2005] 雙面棋盤
一個暴力的想法是并查集，每次操作直接全部重構，時間復雜度是 \(O(n^2m)\) 的。
考慮以行號為下標建線段樹，對于每個節點記錄它對應的第一行和最后一行在只考慮這些格子時在并查集中屬于哪個連通塊。考慮合并，顯然我們要考慮上面那一塊的最后一行和下面那一塊的第一行，重建并查集合并即可。時間復雜度 \(O(nm\log n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
#define gt(x,y) (((x)-1)*n+(y))
using namespace std;
namespace asbt{
int n,m,a[205][205],fa[40005];
int tr[805][2][205],cnt[805][2];
il int find(int x){
return x!=fa[x]?fa[x]=find(fa[x]):x;
}
il void pushup(int id,int l,int r){
for(int i=1;i<=n;i++){
fa[tr[lid][0][i]]=tr[lid][0][i];
fa[tr[lid][1][i]]=tr[lid][1][i];
fa[tr[rid][0][i]]=tr[rid][0][i];
fa[tr[rid][1][i]]=tr[rid][1][i];
}
cnt[id][0]=cnt[lid][0]+cnt[rid][0];
cnt[id][1]=cnt[lid][1]+cnt[rid][1];
int mid=(l+r)>>1;
for(int i=1;i<=n;i++){
if(a[mid][i]==a[mid+1][i]){
int u=find(tr[lid][1][i]),v=find(tr[rid][0][i]);
if(u!=v){
fa[u]=v,cnt[id][a[mid][i]]--;
// cout<<"pushup: "<<i<<'\n';
}
}
}
for(int i=1;i<=n;i++){
tr[id][0][i]=find(tr[lid][0][i]);
tr[id][1][i]=find(tr[rid][1][i]);
}
}
il void build(int id,int l,int r){
if(l==r){
cnt[id][0]=cnt[id][1]=0;
for(int i=1;i<=n;i++){
fa[gt(l,i)]=gt(l,i);
cnt[id][a[l][i]]++;
}
for(int i=1;i<=n;i++){
if(i>1&&a[l][i]==a[l][i-1]){
cnt[id][a[l][i]]--;
fa[gt(l,i)]=fa[gt(l,i-1)];
}
tr[id][0][i]=tr[id][1][i]=fa[gt(l,i)];
}
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
// cout<<l<<' '<<r<<'\n';
pushup(id,l,r);
}
il void upd(int id,int l,int r,int p){
if(l==r){
cnt[id][0]=cnt[id][1]=0;
for(int i=1;i<=n;i++){
fa[gt(l,i)]=gt(l,i);
cnt[id][a[l][i]]++;
}
for(int i=2;i<=n;i++){
if(a[l][i]==a[l][i-1]){
cnt[id][a[l][i]]--;
fa[gt(l,i)]=fa[gt(l,i-1)];
}
tr[id][0][i]=tr[id][1][i]=fa[gt(l,i)];
}
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
upd(lid,l,mid,p);
}
else{
upd(rid,mid+1,r,p);
}
pushup(id,l,r);
}
//il void debug(int id,int l,int r){
// cout<<l<<' '<<r<<' '<<cnt[id][1]<<' '<<cnt[id][0]<<'\n';
// if(l==r){
// return ;
// }
// int mid=(l+r)>>1;
// debug(lid,l,mid);
// debug(rid,mid+1,r);
//}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
build(1,1,n);
// debug(1,1,n);
cin>>m;
while(m--){
int x,y;
cin>>x>>y;
a[x][y]^=1;
upd(1,1,n,x);
cout<<cnt[1][1]<<' '<<cnt[1][0]<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
Q. The Tree
考慮每次 1 u 操作給 \(u\) 的權值加一，如果不考慮二操作，查詢時檢查 \(u\) 的根鏈上有沒有一個后綴和等于這一段的長度即可。可以將每個位置初始值設為 \(-1\)，于是維護最大后綴和即可。
考慮 \(2\) 操作，我們首先要將 \(u\) 的子樹推平成 \(-1\)，但是這樣不完全，因為我們還沒有考慮 \(u\) 根鏈上操作的影響。因此我們需要給 \(u\) 的權值再減去一個 \(v\)，使得 \(u\) 的根鏈最大后綴和為 \(-1\)。顯然 \(v=\operatorname{query}(u)+1\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,sz[maxn],hes[maxn];
int cnt,dfn[maxn],top[maxn];
int fa[maxn],tag[maxn<<2];
vector<int> e[maxn];
struct node{
int sum,suf;
node(int sum=0,int suf=0):sum(sum),suf(suf){}
il node operator+(const node &x)const{
return node(sum+x.sum,max(x.suf,x.sum+suf));
}
}tr[maxn<<2];
il void dfs1(int u){
sz[u]=1;
int mxs=0;
for(int v:e[u]){
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(mxs<sz[v]){
mxs=sz[v],hes[u]=v;
}
}
}
il void dfs2(int u){
dfn[u]=++cnt;
if(!top[u]){
top[u]=u;
}
if(hes[u]){
top[hes[u]]=top[u];
dfs2(hes[u]);
}
for(int v:e[u]){
if(v==hes[u]){
continue;
}
dfs2(v);
}
}
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void pushtag(int id,int l,int r){
tag[id]=1;
tr[id]=node(l-r-1,-1);
}
il void pushdown(int id,int l,int r){
if(tag[id]){
int mid=(l+r)>>1;
pushtag(lid,l,mid);
pushtag(rid,mid+1,r);
tag[id]=0;
}
}
il void build(int id,int l,int r){
if(l==r){
tr[id]=node(-1,-1);
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void add(int id,int l,int r,int p,int v){
if(l==r){
tr[id].sum+=v,tr[id].suf+=v;
return ;
}
pushdown(id,l,r);
int mid=(l+r)>>1;
if(p<=mid){
add(lid,l,mid,p,v);
}
else{
add(rid,mid+1,r,p,v);
}
pushup(id);
}
il void upd(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
pushtag(id,L,R);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r);
}
if(r>mid){
upd(rid,mid+1,R,l,r);
}
pushup(id);
}
il node query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return tr[id];
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(r<=mid){
return query(lid,L,mid,l,r);
}
if(l>mid){
return query(rid,mid+1,R,l,r);
}
return query(lid,L,mid,l,r)+query(rid,mid+1,R,l,r);
}
il int query(int u){
node res=query(1,1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
while(u){
res=query(1,1,n,dfn[top[u]],dfn[u])+res;
u=fa[top[u]];
}
return res.suf;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=2,x;i<=n;i++){
cin>>x;
e[x].pb(i);
}
dfs1(1),dfs2(1);
build(1,1,n);
while(m--){
int opt,u;
cin>>opt>>u;
switch(opt){
case 1:{
add(1,1,n,dfn[u],1);
break;
}
case 2:{
upd(1,1,n,dfn[u],dfn[u]+sz[u]-1);
add(1,1,n,dfn[u],-query(u)-1);
break;
}
default:{
cout<<(query(u)>=0?"black":"white")<<'\n';
break;
}
}
}
return 0;
}
}
int main(){return asbt::main();}
R. [CEOI 2019] Dynamic Diameter
考慮線段樹維護直徑。考慮修改 \((u\xrightarrow{w}v)\to(u\xrightarrow{w'}v)\)，會將 \(v\) 的子樹中的每個點的 \(dis\) 值改變，把 dfs 序拉下來樹狀數組維護即可。然后 \(v\) 子樹內的直徑是不變的，在線段樹上找到這個區間更新上去即可。時間復雜度線性對數方。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=1e5+5;
int n,m,kk,fa[maxn],dfn[maxn],stk[maxn],cnt,sz[maxn],fe[maxn];
vector<int> e[maxn];
struct{
int u,v,w;
}E[maxn];
il void dfs(int u,int fth){
fa[u]=fth,sz[u]=1;
dfn[u]=++cnt,stk[cnt]=u;
for(int v:e[u]){
if(v==fth){
continue;
}
dfs(v,u);
sz[u]+=sz[v];
}
}
struct{
#define lowbit(x) (x&-x)
int tr[maxn];
il void add(int p,int v){
for(;p<=n;p+=lowbit(p)){
tr[p]+=v;
}
}
il int query(int p){
int res=0;
for(;p;p-=lowbit(p)){
res+=tr[p];
}
return res;
}
#undef lowbit
}F;
namespace LCA{
int df[maxn],oula[maxn<<1],idx[maxn<<1],cnt;
il void dfs(int u,int fa){
df[u]=++cnt,oula[cnt]=cnt,idx[cnt]=u;
for(int v:e[u]){
if(v==fa){
continue;
}
dfs(v,u);
oula[++cnt]=df[u];
}
}
struct{
int Log[maxn<<1],st[maxn<<1][19];
il void build(){
for(int i=2;i<=cnt;i++){
Log[i]=Log[i>>1]+1;
}
for(int i=1;i<=cnt;i++){
st[i][0]=oula[i];
}
for(int j=1;j<=Log[cnt];j++){
for(int i=1;i+(1<<j)-1<=cnt;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
il int query(int l,int r){
int p=Log[r-l+1];
return min(st[l][p],st[r-(1<<p)+1][p]);
}
}ST;
il void init(){
dfs(1,0),ST.build();
}
il int lca(int u,int v){
if(df[u]>df[v]){
swap(u,v);
}
return idx[ST.query(df[u],df[v])];
}
il int dis(int u,int v){
return F.query(dfn[u])+F.query(dfn[v])-F.query(dfn[lca(u,v)])*2;
}
}
using LCA::dis;
struct node{
int u,v,w;
node(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
il node operator+(const node &x)const{
int hp[4]={u,v,x.u,x.v};
node res;
for(int i=0;i<=3;i++){
for(int j=i+1;j<=3;j++){
int tmp=dis(hp[i],hp[j]);
if(tmp>res.w){
res=node(hp[i],hp[j],tmp);
}
}
}
return res;
}
}tr[maxn<<2];
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void build(int id,int l,int r){
if(l==r){
tr[id]=node(stk[l],stk[l],0);
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void upd(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return ;
}
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r);
}
if(r>mid){
upd(rid,mid+1,R,l,r);
}
pushup(id);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>kk;
for(int i=1,u,v,w;i<n;i++){
cin>>u>>v>>w;
e[u].pb(v),e[v].pb(u);
E[i]={u,v,w};
}
dfs(1,0),LCA::init();
for(int i=1;i<n;i++){
int &u=E[i].u,&v=E[i].v,w=E[i].w;
if(fa[v]==u){
swap(u,v);
}
fe[u]=w;
F.add(dfn[u],w),F.add(dfn[u]+sz[u],-w);
}
build(1,1,n);
int ans=0;
while(m--){
int x,v;
cin>>x>>v;
x=(x+ans)%(n-1)+1;
v=(v+ans)%kk;
int u=E[x].u;
F.add(dfn[u],v-fe[u]),F.add(dfn[u]+sz[u],fe[u]-v);
fe[u]=v;
upd(1,1,n,dfn[u],dfn[u]+sz[u]-1);
cout<<(ans=tr[1].w)<<'\n';
}
return 0;
}
}
signed main(){return asbt::main();}
S. [JSOI2009] 面試的考驗
首先考慮將所有點對的答案都存起來，于是就變成了一個二維數點問題，掃描線 + 樹狀數組維護即可。
但我們顯然存不下 \(O(n^2)\) 的點對，考慮減少點對數量。不妨令點對 \((i,j)\) 滿足 \(i<j\land a_i<a_j\)，\(a_i>a_j\) 的情況翻轉過來再算一遍即可。對于每個 \(i\) 在它后面的第一個能貢獻的 \(j\) 一定滿足 \(a_j\in[a_i+1,+\infty)\)。\(j\) 之后能再與 \(i\) 產生貢獻的 \(k\) 一定滿足 \(k\in[a_i+1,\frac{a_i+a_j}{2}]\)，因為如果更大那么與 \(j\) 產生貢獻一定是更優的。于是每個 \(i\) 對應的 \(j\) 就是 \(O(\log V)\) 個，點對總數就是 \(O(n\log V)\) 個。找點對用權值線段樹倒著維護一下最小出現位置即可，時間復雜度線性對數方。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e5+5,inf=1e9;
int n,m,a[maxn],ans[maxn];
struct node{
int l,r,id;
il bool operator<(const node &x)const{
return l>x.l;
}
}b[maxn];
struct{
int rt,tot,ls[maxn<<5],rs[maxn<<5],tr[maxn<<5];
il void pushup(int id){
tr[id]=min(tr[ls[id]],tr[rs[id]]);
}
il void build(){
rt=tot=0,ls[0]=rs[0]=0,tr[0]=inf;
}
il void upd(int &id,int l,int r,int p,int v){
if(!id){
id=++tot;
ls[id]=rs[id]=0,tr[id]=inf;
}
if(l==r){
tr[id]=min(tr[id],v);
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
upd(ls[id],l,mid,p,v);
}
else{
upd(rs[id],mid+1,r,p,v);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(!id){
return inf;
}
if(L>=l&&R<=r){
return tr[id];
}
int mid=(L+R)>>1,res=inf;
if(l<=mid){
res=min(res,query(ls[id],L,mid,l,r));
}
if(r>mid){
res=min(res,query(rs[id],mid+1,R,l,r));
}
return res;
}
il void upd(int p,int v){
upd(rt,1,inf,p,v);
}
il int query(int l,int r){
return query(rt,1,inf,l,r);
}
}S;
struct{
#define lowbit(x) (x&-x)
int tr[maxn];
il void init(){
memset(tr,0x3f,sizeof(tr));
}
il void upd(int p,int v){
for(;p<=n;p+=lowbit(p)){
tr[p]=min(tr[p],v);
}
}
il int query(int p){
int res=inf;
for(;p;p-=lowbit(p)){
res=min(res,tr[p]);
}
return res;
}
#undef lowbit
}F;
il void solve(){
vector<pii> vec;
S.build(),F.init();
for(int i=n;i;i--){
int x=inf;
while(x>a[i]){
int y=S.query(a[i]+1,x);
if(y==inf){
break;
}
vec.pb(mp(i,y));
x=(a[i]+a[y])>>1;
}
S.upd(a[i],i);
}
sort(b+1,b+m+1);
for(int i=1,j=0;i<=m;i++){
for(;j<vec.size()&&vec[j].fir>=b[i].l;j++){
F.upd(vec[j].sec,a[vec[j].sec]-a[vec[j].fir]);
}
ans[b[i].id]=min(ans[b[i].id],F.query(b[i].r));
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>b[i].l>>b[i].r;
b[i].id=i;
}
memset(ans,0x3f,sizeof(ans));
solve();
reverse(a+1,a+n+1);
for(int i=1;i<=m;i++){
swap(b[i].l,b[i].r);
b[i].l=n-b[i].l+1;
b[i].r=n-b[i].r+1;
}
solve();
for(int i=1;i<=m;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
T. [agc001_f]Wide Swap
考慮 \(P\) 的逆置換 \(Q\)，于是操作變成了當 \(|Q_i-Q_{i+1}|\ge K\) 時可以交換 \(i\) 和 \(i+1\)。考慮如果 \(|Q_i-Q_j|<K\)，那么它們兩個一定交換不了。回到 \(P\)，也就是說如果 \(|i-j|<K\land P_i<P_j\)，那么最終的答案中一定也有 \(P_i<P_j\)。將所有的 \(i\) 向 \(j\) 連邊，倒著跑個拓撲排序即可。但是邊數太多，考慮優化。顯然 \(i\) 度數為 \(0\) 等價于 \(P_i\) 為 \([i-K+1,i+K-1]\) 中的最大值，線段樹即可，刪去一個點時把 \(P_i\) 改成 \(-\infty\) 就好了。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=5e5+5,inf=1e9;
int n,m,a[maxn],tr[maxn<<2],ans[maxn],cnt;
bool inq[maxn];
priority_queue<int> q;
il int mge(int x,int y){
return a[x]>a[y]?x:y;
}
il void pushup(int id){
tr[id]=mge(tr[lid],tr[rid]);
}
il void build(int id,int l,int r){
if(l==r){
tr[id]=l;
return ;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
pushup(id);
}
il void upd(int id,int l,int r,int p){
if(l==r){
tr[id]=0;
return ;
}
int mid=(l+r)>>1;
if(p<=mid){
upd(lid,l,mid,p);
}
else{
upd(rid,mid+1,r,p);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(l>r){
return 0;
}
if(L>=l&&R<=r){
return tr[id];
}
int mid=(L+R)>>1;
if(r<=mid){
return query(lid,L,mid,l,r);
}
if(l>mid){
return query(rid,mid+1,R,l,r);
}
return mge(query(lid,L,mid,l,r),query(rid,mid+1,R,l,r));
}
il void chk(int p){
if(inq[p]){
return ;
}
if(query(1,1,n,max(p-m+1,1),min(p+m-1,n))==p){
q.push(p),inq[p]=1;
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
a[0]=-inf;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=n;i++){
chk(i);
}
cnt=n;
while(q.size()){
int u=q.top();q.pop();
ans[u]=cnt--;
upd(1,1,n,u);
int v;
if(v=query(1,1,n,max(u-m+1,1),u-1)){
chk(v);
}
if(v=query(1,1,n,u+1,min(u+m-1,n))){
chk(v);
}
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
U. [APIO2018] 新家
首先對時間維做掃描線。
考慮二分答案，現在的問題是求出 \([x-mid,x+mid]\) 中是否有 \(m\) 個顏色。發現并不好求，考慮設 \(pre_i\) 表示 \(i\) 左側第一個與 \(i\) 顏色相同的位置，于是 \((pre_i,i)\) 之間沒有這個顏色。于是我們用線段樹維護每個位置的 \(pre\)，查詢 \(\min[x+mid+1,+\infty)\) 與 \(x-mid\) 的關系即可。至于 \(pre\) 的計算，給每個顏色都開一個 multiset 即可。但是每個位置可能同時有很多個商店，因此對線段樹的每個葉子節點也要開一個 multiset。時間復雜度線性對數方。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lwrb lower_bound
using namespace std;
namespace asbt{
const int maxn=3e5+5,inf=1e9,mx=1e8+1;
int n,m,q,rt,tot,cnt,lsh[maxn],vis[maxn];
int ls[maxn*30],rs[maxn*30],tr[maxn*30],ans[maxn];
struct oprt{
int tim,opt,typ,loc;
oprt(int tim=0,int opt=0,int typ=0,int loc=0)
:tim(tim),opt(opt),typ(typ),loc(loc){}
il bool operator<(const oprt &x)const{
return tim<x.tim||tim==x.tim&&opt<x.opt;
}
}a[maxn*3];
multiset<int> pos[maxn],pre[maxn];
il void pushup(int id){
tr[id]=min(tr[ls[id]],tr[rs[id]]);
}
il void insert(int &id,int l,int r,int x,int v){
if(!id){
id=++tot;
}
if(l==r){
int p=lwrb(lsh+1,lsh+cnt+1,x)-lsh;
if(pre[p].empty()){
pre[p].insert(inf);
}
pre[p].insert(v);
tr[id]=*pre[p].begin();
return ;
}
int mid=(l+r)>>1;
if(x<=mid){
insert(ls[id],l,mid,x,v);
}else{
insert(rs[id],mid+1,r,x,v);
}
pushup(id);
}
il void erase(int id,int l,int r,int x,int v){
if(l==r){
int p=lwrb(lsh+1,lsh+cnt+1,x)-lsh;
pre[p].erase(pre[p].find(v));
tr[id]=*pre[p].begin();
return ;
}
int mid=(l+r)>>1;
if(x<=mid){
erase(ls[id],l,mid,x,v);
}else{
erase(rs[id],mid+1,r,x,v);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(!id){
return inf;
}
if(L>=l&&R<=r){
return tr[id];
}
int mid=(L+R)>>1,res=inf;
if(l<=mid){
res=min(res,query(ls[id],L,mid,l,r));
}
if(r>mid){
res=min(res,query(rs[id],mid+1,R,l,r));
}
return res;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>q;
int tot=0;
for(int i=1,x,t,l,r;i<=n;i++){
cin>>x>>t>>l>>r;
a[++tot]=oprt(l,0,t,x);
a[++tot]=oprt(r,2,t,x);
lsh[++cnt]=x;
}
lsh[++cnt]=mx;
sort(lsh+1,lsh+cnt+1);
cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
for(int i=1,l,y;i<=q;i++){
cin>>l>>y;
a[++tot]=oprt(y,1,i,l);
}
tr[0]=inf;
for(int i=1;i<=m;i++){
pos[i].insert(0);
pos[i].insert(mx);
insert(rt,1,mx,mx,0);
}
sort(a+1,a+tot+1);
int num=0;
for(int i=1;i<=tot;i++){
// cout<<a[i].tim<<' '<<a[i].opt<<' '<<a[i].typ<<' '<<a[i].loc<<'\n';
int t=a[i].typ,x=a[i].loc;
switch(a[i].opt){
case 0:{
if(++vis[t]==1){
num++;
}
auto it=pos[t].insert(x);
insert(rt,1,mx,x,*prev(it));
erase(rt,1,mx,*next(it),*prev(it));
insert(rt,1,mx,*next(it),x);
break;
}
case 1:{
if(num<m){
ans[t]=-1;
continue;
}
int l=0,r=mx;
while(l<r){
int mid=(l+r)>>1;
if(query(rt,1,mx,min(x+mid+1,mx),mx)<max(x-mid,1)){
l=mid+1;
}else{
r=mid;
}
}
ans[t]=l;
break;
}
default:{
if(vis[t]--==1){
num--;
}
auto it=pos[t].find(x);
erase(rt,1,mx,x,*prev(it));
erase(rt,1,mx,*next(it),x);
insert(rt,1,mx,*next(it),*prev(it));
pos[t].erase(it);
break;
}
}
}
for(int i=1;i<=q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號