这道题 想到解法很简单关键是写的时候比较ex 至少我写了1个多小时才写完还有颇多的细节处理。
树刨之后线段树维护颜色这个很好维护因为我们都写过线段树维护的区间最大连续子段和。
然后 维护一下区间修改一下 然后 查询一下即可。 关键是查询好吧。
对于查询我们显然 是边求LCA边查询然后边统计答案 对于l r这种答案必须得特殊处理一下 考虑 我们l r不管是在左边还是右边只要是合理的拼接就可以成功 然后 对于l 我们想一下这是线段树上的 我们要把查询出来的结果翻转显然 观察你的线段树和你所画的图即可。
r的话可以不用翻转也是观察图 最后合并即可。
//#incldue<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define lv(x) t[x].lv #define rv(x) t[x].rv #define tag(x) t[x].tag #define INF 2147483646 #define tn ver[i] using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } 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*10+ch-‘0‘;ch=getchar();} return x*f; } inline void put(int x) { x<0?putchar(‘-‘),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+‘0‘,x/=10; num==0?putchar(‘0‘):0; while(num)putchar(ch[num--]); putchar(‘\n‘);return; } const int MAXN=100002; int n,m,len,cnt; int lin[MAXN<<1],nex[MAXN<<1],ver[MAXN<<1]; int f[MAXN],top[MAXN],son[MAXN],d[MAXN],a[MAXN]; int sz[MAXN],id[MAXN],ans[MAXN],pos[MAXN]; char b[2]; struct wy { int l,r; int sum; int lv,rv,tag; wy(){lv=rv=tag=sum=l=r=0;} }t[MAXN<<2]; void add(int x,int y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline void dfs(int x,int father) { d[x]=d[father]+1; sz[x]=1;f[x]=father; for(int i=lin[x];i;i=nex[i]) { if(tn==father)continue; dfs(tn,x); sz[x]+=sz[tn]; if(sz[tn]>sz[son[x]])son[x]=tn; } } inline void dp(int x,int father) { id[x]=++cnt;pos[cnt]=a[x]; top[x]=father; if(!son[x])return; dp(son[x],father); for(int i=lin[x];i;i=nex[i]) if(tn!=f[x]&&tn!=son[x])dp(tn,tn); return; } inline void build(int p,int l,int r) { l(p)=l;r(p)=r; if(l==r){lv(p)=rv(p)=pos[l];sum(p)=1;return;} int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); sum(p)=sum(p<<1)+sum(p<<1|1)-((rv(p<<1)==lv(p<<1|1))?1:0); lv(p)=lv(p<<1);rv(p)=rv(p<<1|1); return; } inline void pushdown(int p) { sum(p<<1)=sum(p<<1|1)=1; lv(p<<1)=rv(p<<1)=lv(p<<1|1)=rv(p<<1|1)=tag(p); tag(p<<1)=tag(p<<1|1)=tag(p); tag(p)=0;return; } inline wy ask(int p,int l,int r) { if(l<=l(p)&&r>=r(p))return t[p]; int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); wy a,b; if(l<=mid)a=ask(p<<1,l,r); if(r>mid)b=ask(p<<1|1,l,r); sum(p)=sum(p<<1)+sum(p<<1|1)-(rv(p<<1)==lv(p<<1|1)?1:0); lv(p)=lv(p<<1);rv(p)=rv(p<<1|1); if(!a.sum)return b; if(!b.sum)return a; a.sum=a.sum+b.sum-(a.rv==b.lv?1:0); a.rv=b.rv; return a; } inline int Task(int x,int y) { int fx=top[x],fy=top[y]; wy l,r,tmp;//l代表x r代表y while(fx!=fy) { if(d[fx]>d[fy]) { tmp=ask(1,id[fx],id[x]); swap(tmp.lv,tmp.rv); x=f[fx];fx=top[x]; if(!l.sum){l=tmp;continue;} l.sum=l.sum+tmp.sum-(l.rv==tmp.lv?1:0); l.rv=tmp.rv; } else { tmp=ask(1,id[fy],id[y]); y=f[fy];fy=top[y]; if(!r.sum){r=tmp;continue;} r.sum=r.sum+tmp.sum-(r.lv==tmp.rv?1:0); r.lv=tmp.lv; } } if(id[x]>id[y]) { tmp=ask(1,id[y],id[x]); swap(tmp.lv,tmp.rv); if(!l.sum)l=tmp; else { l.sum=l.sum+tmp.sum-(l.rv==tmp.lv?1:0); l.rv=tmp.rv; } } else { tmp=ask(1,id[x],id[y]); if(!r.sum)r=tmp; else { r.sum=r.sum+tmp.sum-(r.lv==tmp.rv?1:0); r.lv=tmp.lv; } } tmp.sum=l.sum+r.sum-(l.rv==r.lv?1:0); return tmp.sum; } inline void change(int p,int l,int r,int k) { if(l<=l(p)&&r>=r(p)) { tag(p)=k;sum(p)=1; lv(p)=rv(p)=k; return; } int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)change(p<<1,l,r,k); if(r>mid)change(p<<1|1,l,r,k); sum(p)=sum(p<<1)+sum(p<<1|1)-(rv(p<<1)==lv(p<<1|1)?1:0); lv(p)=lv(p<<1);rv(p)=rv(p<<1|1); return; } inline void Tchange(int x,int y,int z) { int fx=top[x],fy=top[y]; while(fx!=fy) { if(d[fx]<d[fy])swap(fx,fy),swap(x,y); change(1,id[fx],id[x],z); x=f[fx];fx=top[x]; } if(id[x]<id[y])swap(x,y); change(1,id[y],id[x],z); return; } int main() { //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<n;++i) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0);dp(1,1); build(1,1,cnt); for(int i=1;i<=m;++i) { int x,y,z; scanf("%s",b+1); x=read();y=read(); if(b[1]==‘Q‘)put(Task(x,y)); else z=read(),Tchange(x,y,z); } return 0; }
下面是今天对拍所用文件 对拍真的爽。
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<queue> #include<deque> #include<vector> #include<map> #include<stack> #include<set> #include<bitset> #include<cstdlib> using namespace std; int main() { for(int t=1;t<=100000;t++) { system("E:\\random.exe"); double st=clock(); system("E:\\bf.exe"); double ed=clock(); system("E:\\sol.exe"); if(system("fc E:\\2.out E:\\1.out")) { puts("Wrong Answer"); return 0; } else { printf("Accepted,测试点 #%d,用时 %.0lfms\n",t,ed-st); } } return 0; }
//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<algorithm> #include<queue> #include<deque> #include<vector> #include<map> #include<stack> #include<set> #include<bitset> #include<cstdlib> using namespace std; int n,m; int a[1000]; int f[1000],cnt; int getfather(int x){return x==f[x]?x:f[x]=getfather(f[x]);} int main() { freopen("1.in","w",stdout); srand(time(0)); n=rand()%5+2; m=rand()%5+1; cout<<n<<‘ ‘<<m<<endl; for(int i=1;i<=n;++i)cout<<rand()%n+1<<‘ ‘; cout<<endl; for(int i=1;i<=n;++i)f[i]=i; while(cnt<n-1) { int x=rand()%n+1; int y=rand()%n+1; int xx=getfather(x); int yy=getfather(y); if(xx==yy)continue; f[xx]=yy;++cnt; cout<<x<<‘ ‘<<y<<endl; } for(int i=1;i<=m;++i) { if(i&1) { cout<<"Q"<<endl; int l=rand()%n+1; int r=rand()%n+1; cout<<l<<‘ ‘<<r<<‘ ‘<<endl; } else { cout<<"C"<<endl; int l=rand()%n+1; int r=rand()%n+1; int z=rand()%1000000000+1; cout<<l<<‘ ‘<<r<<‘ ‘<<z<<endl; } } return 0; }
没有思考好细节下次一定要想好。
可能心有点乱了 必须回去学习文化课的决定已经下好了 。我一定会对自己负责的。也第一定不会自己辜负自己的。
就算是为了自己吧。看我神威 无坚不摧！
这道题是一个树链刨分但我手滑了好几次 比如dp写成dfs 没有push up 还有long long 没有搞全。
关于long long这个问题 我想是应该计算一下空间如果空间足够那全部都开long long不够的话那就只能局部开了 把所有有可能爆long long的地方全开上，不然wa了可就难受 退役了。不开longlong见祖宗啊。
//#incldue<bits/stdc++.h> #include<iostream> #include<queue> #include<iomanip> #include<cctype> #include<cstdio> #include<deque> #include<utility> #include<cmath> #include<ctime> #include<cstring> #include<string> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<map> #include<set> #include<bitset> #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define tag(x) t[x].tag #define INF 2147483646 #define ll long long using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } 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*10+ch-‘0‘;ch=getchar();} return x*f; } inline void put(ll x) { x<0?putchar(‘-‘),x=-x:0; int num=0;char ch[50]; while(x)ch[++num]=x%10+‘0‘,x/=10; num==0?putchar(‘0‘):0; while(num)putchar(ch[num--]); putchar(‘\n‘);return; } const int MAXN=100002; int n,m,cnt,len; int a[MAXN],pos[MAXN],id[MAXN],f[MAXN]; int top[MAXN],d[MAXN],son[MAXN],sz[MAXN]; int lin[MAXN<<1],ver[MAXN<<1],nex[MAXN<<1]; struct wy { int l,r; ll sum; ll tag; }t[MAXN<<2]; inline void add(int x,int y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } inline void dfs(int x,int father) { f[x]=father;sz[x]=1; d[x]=d[father]+1; for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn==father)continue; dfs(tn,x); sz[x]+=sz[tn]; if(sz[son[x]]<sz[tn])son[x]=tn; } return; } inline void dp(int x,int father) { top[x]=father; id[x]=++cnt; pos[cnt]=a[x]; if(!son[x])return; dp(son[x],father); for(int i=lin[x];i;i=nex[i]) { int tn=ver[i]; if(tn!=f[x]&&tn!=son[x]) dp(tn,tn); } return; } inline void build(int p,int l,int r) { l(p)=l;r(p)=r; if(l==r){sum(p)=pos[l];return;} int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); sum(p)=sum(p<<1)+sum(p<<1|1); } inline void pushdown(int p) { ll mid=(l(p)+r(p))>>1; tag(p<<1)+=tag(p); tag(p<<1|1)+=tag(p); sum(p<<1)+=(mid-l(p)+1)*tag(p); sum(p<<1|1)+=(r(p)-mid)*tag(p); tag(p)=0;return; } inline void change(int p,int l,int r,ll k) { if(l<=l(p)&&r>=r(p)) { tag(p)+=k; sum(p)+=(r(p)-l(p)+1)*k; return; } int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)change(p<<1,l,r,k); if(r>mid)change(p<<1|1,l,r,k); sum(p)=sum(p<<1)+sum(p<<1|1); return; } inline ll ask(int p,int l,int r) { if(l<=l(p)&&r>=r(p))return sum(p); ll cnt=0; int mid=(l(p)+r(p))>>1; if(tag(p))pushdown(p); if(l<=mid)cnt+=ask(p<<1,l,r); if(r>mid)cnt+=ask(p<<1|1,l,r); sum(p)=sum(p<<1)+sum(p<<1|1); return cnt; } inline ll Task(int x,int y) { int fx=top[x];int fy=top[y]; ll ans=0; while(fx!=fy) { ans+=ask(1,id[fx],id[x]); x=f[fx];fx=top[x]; } ans+=ask(1,id[y],id[x]); return ans; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<n;++i) { int x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0);dp(1,1); build(1,1,cnt); for(int i=1;i<=n;++i) { int p,x,y; p=read(); switch(p) { case 1:x=read();y=read(); change(1,id[x],id[x],y); break; case 2:x=read();y=read(); change(1,id[x],id[x]+sz[x]-1,y); break; case 3:x=read(); put(Task(x,1)); break; } } return 0; }
值得一提的是这个问题可以使用线段树直接解决 我指的是单指这道题。
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<iomanip> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<algorithm> #include<cctype> #include<utility> #include<set> #include<bitset> #include<queue> #include<stack> #include<deque> #include<map> #include<vector> #include<ctime> #define l(x) t[x].l #define r(x) t[x].r #define sum(x) t[x].sum #define c(x) t[x].add #define v(x) t[x].k using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline long long read() { long long 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*10+ch-‘0‘;ch=getchar();} return x*f; } inline void put(long long x) { x<0?putchar(‘-‘),x=-x:0; long long num=0;char ch[50]; while(x)ch[++num]=x%10+‘0‘,x/=10; num==0?putchar(‘0‘):0; while(num)putchar(ch[num--]); putchar(10);return; } const long long MAXN=200002; struct wy1{long long l,r;}s[MAXN]; struct wy { long long l,r,sum; long long k;//k表示属性 long long add; }t[MAXN<<2]; long long n,m; long long lin[MAXN],ver[MAXN],nex[MAXN],len=0; long long cnt,a[MAXN],b[MAXN],vis[MAXN]; void add(long long x,long long y) { ver[++len]=y; nex[len]=lin[x]; lin[x]=len; } void dfs(long long x,long long father) { s[x].l=++cnt;vis[cnt]=1; for(long long i=lin[x];i;i=nex[i]) { long long tn=ver[i]; if(tn==father)continue; dfs(tn,x); } s[x].r=++cnt; } void build(long long p,long long l,long long r) { l(p)=l;r(p)=r; if(l==r){if(vis[l])v(p)=1;else v(p)=-1;return;} long long mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); v(p)=v(p<<1)+v(p<<1|1); return; } void pushdown(long long p) { sum(p<<1)+=v(p<<1)*c(p); sum(p<<1|1)+=v(p<<1|1)*c(p); c(p<<1)+=c(p); c(p<<1|1)+=c(p); c(p)=0;return; } void change(long long p,long long l,long long r,long long d) { if(l<=l(p)&&r>=r(p)) { c(p)+=d; sum(p)+=v(p)*d; return; } if(c(p))pushdown(p); long long mid=(l(p)+r(p))>>1; if(l<=mid)change(p<<1,l,r,d); if(r>mid)change(p<<1|1,l,r,d); sum(p)=sum(p<<1)+sum(p<<1|1); return; } long long ask(long long p,long long l,long long r) { if(l<=l(p)&&r>=r(p))return sum(p); if(c(p))pushdown(p); long long cnt=0; long long mid=(l(p)+r(p))>>1; if(l<=mid)cnt+=ask(p<<1,l,r); if(r>mid)cnt+=ask(p<<1|1,l,r); return cnt; } int main() { //freopen("1.in","r",stdin); int __size__ = 20 << 20; // 20MB char *__p__ = (char*)malloc(__size__) + __size__; __asm__("movl %0, %%esp\n" :: "r"(__p__)); n=read();m=read(); for(long long i=1;i<=n;i++)a[i]=read(); for(long long i=1;i<n;i++) { long long x,y; x=read();y=read(); add(x,y);add(y,x); } dfs(1,0); //for(long long i=1;i<=n;i++)cout<<i<<‘ ‘<<s[i].v<<‘ ‘<<s[i].l<<‘ ‘<<s[i].r<<endl; build(1,1,cnt); for(int i=1;i<=n;i++) { change(1,s[i].l,s[i].l,a[i]); change(1,s[i].r,s[i].r,a[i]); } for(long long i=1;i<=m;i++) { long long p,x,d; p=read(); if(p==1) { x=read();d=read(); change(1,s[x].l,s[x].l,d); change(1,s[x].r,s[x].r,d); } if(p==2) { x=read();d=read(); change(1,s[x].l,s[x].r,d); } if(p==3) { x=read(); put(ask(1,1,s[x].l)); } } return 0; }
以前写的这道题 运用的是dfs序的变形刚好能解决这道题 mlogn 比树刨快。
原文：https://www.cnblogs.com/chdy/p/10815701.html
