[kuangbin带你飞]特集七線分树题解(未完)
47893 ワード
[kuangbin帯你飛]特集七線分樹
問題解:A経典の単点更新、区間求和:
B.古典的な単点更新、区間クエリ最大値
C.区間更新、区間照会区間更新に遅延更新を加えたpush_down操作とは、現在のノードの左右の息子ノードを更新または照会する際に、事前に左右の息子ノードを更新し、現在の区間を照会してから下のノードを更新することを保証することです.これが怠惰なlazy propagation操作です.
D区間点染色問題先離散化処理点範囲,区間染色問題は実際には詳細な問題解である
E区間修正、区間加算
F区間線分染色問題
G未修正区間最値問題
H.区間開方の修正,区間求和が怠惰にならないように見える区間求和問題.しかし、テーマには整数和を求めるだけの要求が隠されており、テーマのすべての数の和が2^63を超えないことから、区間と何度も更新されないと1になると推定できます.区間更新時に枝切りがあり、push_は不要ですdown操作.
I連続区間の最大と問題解を求める
J.dfs序+区間染色染色題意:1つの木(n<=50000)を与え、2つの操作(q<=50000):1.ノード情報を更新すると、その子孫ノードは同じ情報に更新される.2.いずれかのノードの情報を照会します.
構想:ツリーのルートからdfsシーケンスを1回開始し、l,rの2つの配列で各ノードに割り当てられる範囲を再構築します.例えば、ルートノードは[1,n]で、葉ノードまでです.そして区間点染色問題です.
“`
問題解:A経典の単点更新、区間求和:
#include
using namespace std;
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=5e4+10;
int n,sum[N<<2];
void push_up(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
scanf("%d",&sum[rt]);
return;
}
int m=l+r >>1;
build(lson); build(rson);
push_up(rt);
}
void update(int o,int v,int l,int r,int rt){
if(l==r){
sum[rt]+=v;
return;
}
int m=l+r >>1;
if(o<=m) update(o,v,lson);
else update(o,v,rson);
push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r) return sum[rt];
int m=l+r>>1;
int res=0;
if(L<=m) res+=query(L,R,lson);
if(R>m) res+=query(L,R,rson);
return res;
}
int main(){
int T; scanf("%d",&T);
int cas = 0;
while(T--) {
printf("Case %d:
", ++cas);
scanf("%d",&n);
build(root);
char op[10]; int x, y;
while(scanf("%s",op)) {
if(op[0] == 'E') break;
scanf("%d%d",&x,&y);
if(op[0] == 'Q') printf("%d
",query(x, y,root));
else if(op[0] == 'A') update(x, y, root);
else if(op[0] == 'S') update(x, -y, root);
}
}
}
B.古典的な単点更新、区間クエリ最大値
#include
using namespace std;
const int N=2e5+10,inf=0x37373737;
int maxx[N*4];
void push_up(int x){
maxx[x]=max(maxx[x<<1],maxx[x<<1|1]);
}
void build(int x,int l,int r){
if(l==r){
scanf("%d",&maxx[x]);
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
push_up(x);
}
void update(int o,int v,int l,int r,int x){
if(l==r){
maxx[x]=v;
return;
}
int mid=(l+r)>>1;
if(mid>=o) update(o,v,l,mid,x<<1);
else update(o,v,mid+1,r,x<<1|1);
push_up(x);
}
int query(int L,int R,int l,int r,int x){
if(L<=l&&R>=r) return maxx[x];
int res=-inf;
int mid=(l+r)>>1;
if(L<=mid) res=max(res,query(L,R,l,mid,x<<1));
if(R>mid) res=max(res,query(L,R,mid+1,r,x<<1|1));
return res;
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
build(1,1,n);
while(m--){
char op[2];scanf("%s",op);
int a,b;scanf("%d%d",&a,&b);
if(op[0]=='Q') printf("%d
",query(a,b,1,n,1));
else update(a,b,1,n,1);
}
}
}
C.区間更新、区間照会区間更新に遅延更新を加えたpush_down操作とは、現在のノードの左右の息子ノードを更新または照会する際に、事前に左右の息子ノードを更新し、現在の区間を照会してから下のノードを更新することを保証することです.これが怠惰なlazy propagation操作です.
#include
#include
#include
using namespace std;
typedef long long ll;
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int N=1e5+6;
ll sum[N<<4],add[N<<4];
int n,q;
void push_up(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int m){
if(add[rt]){
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
sum[rt<<1]+=add[rt]*(m-(m>>1));
sum[rt<<1|1]+=add[rt]*(m>>1);
add[rt]=0;
}
}
void build(int l,int r,int rt){
add[rt]=0;
if(l==r){
scanf("%lld",&sum[rt]);
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(rt);
}
void update(int L,int R,int v,int l,int r,int rt){
if(L<=l&&r<=R){
add[rt]+=v;
sum[rt]+=(ll)v*(r-l+1);
return;
}
push_down(rt,r-l+1);
int m=l+r >>1;
if(L<=m) update(L,R,v,lson);
if(R>m) update(L,R,v,rson);
push_up(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R) return sum[rt];
push_down(rt,r-l+1);
int m=(l+r)>>1;
ll res=0;
if(L<=m) res+=query(L,R,lson);
if(R>m) res+=query(L,R,rson);
return res;
}
int main(){
while(scanf("%d%d",&n,&q)==2){
build(root);
while(q--){
char op[2]; int x, y, z;
scanf("%s%d%d", op, &x, &y);
if(op[0] == 'Q') printf("%lld
", query(x,y,root));
else {
scanf("%d",&z);
update(x,y,z, root);
}
}
}
}
D区間点染色問題先離散化処理点範囲,区間染色問題は実際には詳細な問題解である
#include
#include
#include
#include
#include
#include
using namespace std;
const int N=1e4+10;
int x1[N],x2[N],vis[6*N*4],cnt[N],ans,n;
int compress(int *x1,int *x2,int w){
vector<int> xs;
for(int i=1;i<=n;i++){
for(int d=-1;d<=1;d++){
int tx1=x1[i]+d,tx2=x2[i]+d;
if(1<=tx1&&tx1<=w) xs.push_back(tx1);
if(1<=tx2&&tx2<=w) xs.push_back(tx2);
}
}
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
for(int i=1;i<=n;i++){
x1[i]=find(xs.begin(),xs.end(),x1[i])-xs.begin()+1;
x2[i]=find(xs.begin(),xs.end(),x2[i])-xs.begin()+1;
}
return xs.size();
}
void push_down(int rt){
if(vis[rt]){
vis[rt<<1]=vis[rt<<1|1]=vis[rt];
vis[rt]=0;
}
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){
vis[rt]=c;
return;
}
int m=(l+r)>>1;
push_down(rt);
if(L<=m) update(L,R,c,l,m,rt<<1);
if(R>m) update(L,R,c,m+1,r,rt<<1|1);
}
void query(int l,int r,int rt){
if(vis[rt]){
if(!cnt[vis[rt]]){
ans++;cnt[vis[rt]]=1;
}
return;
}
if(l==r) return;
int m=l+r>>1;
query(l,m,rt<<1);
query(m+1,r,rt<<1|1);
}
int main(){
int T;scanf("%d",&T);
while(T--){
int w=0;scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",x1+i,x2+i);
}
w=compress(x1,x2,1e7);
//cout<
memset(cnt,0,sizeof(cnt));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
update(x1[i],x2[i],i,1,w,1);
}
ans=0;
//cout<
query(1,w,1);
printf("%d
",ans);
}
}
E区間修正、区間加算
#include
using namespace std;
typedef long long ll;
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int N=1e5+6;
ll sum[N<<4],add[N<<4];
int n,q;
void push_up(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void push_down(int rt,int m){
if(add[rt]){
add[rt<<1]=add[rt];
add[rt<<1|1]=add[rt];
sum[rt<<1]=add[rt]*(m-(m>>1));
sum[rt<<1|1]=add[rt]*(m>>1);
add[rt]=0;
}
}
void build(int l,int r,int rt){
add[rt]=0;
if(l==r){
sum[rt]=1;
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
push_up(rt);
}
void update(int L,int R,int v,int l,int r,int rt){
if(L<=l&&r<=R){
add[rt]=v;
sum[rt]=(ll)v*(r-l+1);
return;
}
push_down(rt,r-l+1);
int m=l+r >>1;
if(L<=m) update(L,R,v,lson);
if(R>m) update(L,R,v,rson);
push_up(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R) return sum[rt];
push_down(rt,r-l+1);
int m=(l+r)>>1;
ll res=0;
if(L<=m) res+=query(L,R,lson);
if(R>m) res+=query(L,R,rson);
return res;
}
int main(){
int T,cnt=1;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&q);
build(root);
while(q--){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
update(a,b,c,root);
}
printf("Case %d: The total value of the hook is %lld.
",cnt++,query(1,n,root));
}
}
F区間線分染色問題
#include
using namespace std;
const int N=1e4;
int vis[N<<2],col[N],last;
void push_down(int rt){
if(vis[rt]>=0){
vis[rt<<1]=vis[rt<<1|1]=vis[rt];
vis[rt]=-1;
}
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){
vis[rt]=c;
return;
}
int m=(l+r)>>1;
push_down(rt);
if(L<=m) update(L,R,c,l,m,rt<<1);
if(R>m) update(L,R,c,m+1,r,rt<<1|1);
}
void query(int l,int r,int rt){
if(l==r){
if(vis[rt]!=last) col[vis[rt]]++;
last=vis[rt];
return;
}
push_down(rt);
int m=l+r>>1;
query(l,m,rt<<1);
query(m+1,r,rt<<1|1);
}
int main(){
int n;
while(~scanf("%d",&n)){
memset(vis,-1,sizeof(vis));
memset(col,0,sizeof(col));
for(int i=0;iint a,b,c;scanf("%d%d%d",&a,&b,&c);
if(a+1<=b) update(a+1,b,c,1,8000,1);
}
last=-1;
query(1,8000,1);
for(int i=0;i<=8000;i++){
if(col[i]>0) printf("%d %d
",i,col[i]);
}
printf("
");
}
}
G未修正区間最値問題
#include
#include
#include
using namespace std;
const int N=1<<16;
int dmin[N][16],dmax[N][16],n,m,A[N];
void RMQ_init(){
for(int i=0;i0]=A[i],dmax[i][0]=A[i];
for(int j=1;(1<for(int i=0;i+(1<11],dmin[i+(1<1))][j-1]);
dmax[i][j]=max(dmax[i][j-1],dmax[i+(1<1))][j-1]);
}
}
}
int rmq(int l,int r,int ok){//ok=0 ,ok=1
int k=0;
while((1<1))<=r-l+1) k++;
return ok==0 ? min(dmin[l][k],dmin[r-(1<1][k]) : max(dmax[l][k],dmax[r-(1<1][k]);
}
int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=0;i"%d",&A[i]);
RMQ_init();
while(m--){
int a,b;scanf("%d%d",&a,&b);
printf("%d
",rmq(a-1,b-1,1)-rmq(a-1,b-1,0));
}
}
}
H.区間開方の修正,区間求和が怠惰にならないように見える区間求和問題.しかし、テーマには整数和を求めるだけの要求が隠されており、テーマのすべての数の和が2^63を超えないことから、区間と何度も更新されないと1になると推定できます.区間更新時に枝切りがあり、push_は不要ですdown操作.
#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
ll sum[N<<2];
void push_up(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
scanf("%lld",&sum[rt]);
return;
}
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
push_up(rt);
}
void update(int L,int R,int l,int r,int rt){
if(sum[rt]==r-l+1) return;
if(l==r){
sum[rt]=sqrt(sum[rt]);
return;
}
int m=(l+r)>>1;
if(L<=m) update(L,R,lson);
if(R>m) update(L,R,rson);
push_up(rt);
}
ll query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sum[rt];
}
ll res=0;
int m=(l+r)>>1;
if(L<=m) res+=query(L,R,lson);
if(R>m) res+=query(L,R,rson);
return res;
}
int main(){
int n,cas=1;
while(scanf("%d",&n)==1){
build(root);
int q;scanf("%d",&q);
printf("Case #%d:
",cas++);
while(q--){
int o,a,b;scanf("%d%d%d",&o,&a,&b);
if(a>b) swap(a,b);
if(o==0) update(a,b,1,n,1);
else printf("%lld
",query(a,b,1,n,1));
}
printf("
");
}
}
I連続区間の最大と問題解を求める
#include
using namespace std;
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=5e4+10;
int lsum[N<<2],rsum[N<<2],sta[N],n,q;
void push_up(int rt,int m){
lsum[rt]=lsum[rt<<1];
rsum[rt]=rsum[rt<<1|1];
if(lsum[rt<<1]==m-(m>>1)) lsum[rt]+=lsum[rt<<1|1];
if(rsum[rt<<1|1]==m>>1) rsum[rt]+=rsum[rt<<1];
}
void build(int l,int r,int rt){
lsum[rt]=rsum[rt]=r-l+1;
if(l==r) return;
int m=l+r >>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
}
void update(int o,int v,int l,int r,int rt){
if(l==r){
lsum[rt]=rsum[rt]=v;
return;
}
int m=l+r>>1;
if(o<=m) update(o,v,lson);
else update(o,v,rson);
push_up(rt,r-l+1);
}
int query(int o,int l,int r,int rt){
if(l==r) return 0;
int m=l+r >>1;
if(o>=m-rsum[rt<<1]+1&&o<=m+lsum[rt<<1|1]){
return rsum[rt<<1]+lsum[rt<<1|1];
}
if(o<=m) return query(o,lson);
else return query(o,rson);
}
int main(){
while(~scanf("%d%d",&n,&q)){
build(root);
int t=0;
while(q--){
char op[2];scanf("%s",op);
if(op[0]=='R'){
int x=sta[--t];
update(x,1,root);
}
else{
int x;scanf("%d",&x);
if(op[0]=='D'){
update(x,0,root);
sta[t++]=x;
}
else printf("%d
",query(x,root));
}
}
}
}
J.dfs序+区間染色染色題意:1つの木(n<=50000)を与え、2つの操作(q<=50000):1.ノード情報を更新すると、その子孫ノードは同じ情報に更新される.2.いずれかのノードの情報を照会します.
構想:ツリーのルートからdfsシーケンスを1回開始し、l,rの2つの配列で各ノードに割り当てられる範囲を再構築します.例えば、ルートノードは[1,n]で、葉ノードまでです.そして区間点染色問題です.
#include
using namespace std;
const int N=5e4+10;
int l[N],r[N],vis[N<<2];
#define root 1,n,1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
void push_down(int rt){
if(vis[rt]>=0){
vis[rt<<1]=vis[rt<<1|1]=vis[rt];
vis[rt]=-1;
}
}
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){
vis[rt]=c;
return;
}
int m=(l+r)>>1;
push_down(rt);
if(L<=m) update(L,R,c,l,m,rt<<1);
if(R>m) update(L,R,c,m+1,r,rt<<1|1);
}
int query(int o,int l,int r,int rt){
if(l==r){
return vis[rt];
}
push_down(rt);
int m=l+r>>1;
if(o<=m)return query(o,lson);
else return query(o,rson);
}
vector<int>E[N];
int cnt;
bool use[N];
void dfs(int u){
l[u]=++cnt;
for(int i=0;iint v=E[u][i];
dfs(v);
}
r[u]=cnt;
}
int main(){
int T,cas=1;scanf("%d",&T);
while(T--){
cnt=0;
int n;scanf("%d",&n);
for(int i=0;i<=n;i++) E[i].clear();
memset(use,false,sizeof(use));
for(int i=0;i1;i++){
int a,b;scanf("%d%d",&a,&b);
E[b].push_back(a);
use[a]=true;
}
for(int i=1;i<=n;i++){
if(!use[i]){
dfs(i);
break;
}
}
printf("Case #%d:
",cas++);
memset(vis,-1,sizeof(vis));
int q;scanf("%d",&q);
while(q--){
char op[2];scanf("%s",op);
if(op[0]=='C'){
int x;scanf("%d",&x);
printf("%d
",query(l[x],1,cnt,1));
}
else{
int a,b;scanf("%d%d",&a,&b);
update(l[a],r[a],b,1,cnt,1);
}
}
}
}
“`