【做題記錄】2025刷題計(jì)劃--線段樹
A. 「SDOI2014」旅行
給每個(gè)宗教開一棵線段樹，樹剖 \(+\) 線段樹單點(diǎn)修改區(qū)間查詢即可。需要?jiǎng)討B(tài)開點(diǎn)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define int ll
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,maxm=5e6+5;
int n,m,a[maxn],b[maxn],cnt;
int top[maxn],fa[maxn],dfn[maxn];
int sz[maxn],hes[maxn],dep[maxn];
vector<int> e[maxn];
il void dfs1(int u){
dep[u]=dep[fa[u]]+1;
sz[u]=1;
int mxs=0;
for(int v:e[u]){
if(v==fa[u]){
continue;
}
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==fa[u]||v==hes[u]){
continue;
}
dfs2(v);
}
}
int rt[maxn],ls[maxm],rs[maxm];
int tot,sum[maxm],mx[maxm];
il void pushup(int id){
sum[id]=sum[ls[id]]+sum[rs[id]];
mx[id]=max(mx[ls[id]],mx[rs[id]]);
}
il void upd(int &id,int l,int r,int pos,int val){
if(!id){
id=++tot;
}
if(l==r){
sum[id]=mx[id]=val;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid){
upd(ls[id],l,mid,pos,val);
}
else{
upd(rs[id],mid+1,r,pos,val);
}
pushup(id);
}
il int qsum(int id,int L,int R,int l,int r){
if(!id){
return 0;
}
if(L>=l&&R<=r){
return sum[id];
}
int mid=(L+R)>>1,res=0;
if(l<=mid){
res+=qsum(ls[id],L,mid,l,r);
}
if(r>mid){
res+=qsum(rs[id],mid+1,R,l,r);
}
return res;
}
il int qmx(int id,int L,int R,int l,int r){
if(!id){
return 0;
}
if(L>=l&&R<=r){
return mx[id];
}
int mid=(L+R)>>1,res=0;
if(l<=mid){
res=max(res,qmx(ls[id],L,mid,l,r));
}
if(r>mid){
res=max(res,qmx(rs[id],mid+1,R,l,r));
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/10485796.0;}
}
signed main(){
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i])read(b[i]);
}
for(int i=1,u,v;i<n;i++){
read(u)read(v);
e[u].pb(v),e[v].pb(u);
}
dfs1(1),dfs2(1);
for(int i=1;i<=n;i++){
upd(rt[b[i]],1,n,dfn[i],a[i]);
}
while(m--){
char opt[5];
int u,v;
scanf(" %s",opt+1);
read(u)read(v);
switch(opt[2]){
case 'C':{
upd(rt[b[u]],1,n,dfn[u],0);
b[u]=v;
upd(rt[b[u]],1,n,dfn[u],a[u]);
break;
}
case 'W':{
a[u]=v;
upd(rt[b[u]],1,n,dfn[u],a[u]);
break;
}
case 'S':{
int res=0,x=b[u];
while(top[u]!=top[v]){
// puts("666");
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
res+=qsum(rt[x],1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
res+=qsum(rt[x],1,n,dfn[u],dfn[v]);
printf("%lld\n",res);
break;
}
default:{
int res=0,x=b[u];
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
res=max(res,qmx(rt[x],1,n,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
res=max(res,qmx(rt[x],1,n,dfn[u],dfn[v]));
printf("%lld\n",res);
break;
}
}
}
return 0;
}
}
signed main(){return asbt::main();}
B. 康娜的線段樹
對(duì)于每個(gè)葉子節(jié)點(diǎn)，設(shè)深度為 \(dep\)，則對(duì)答案的貢獻(xiàn)為 \(a_i\times\sum_{i=0}^{dep}\frac{1}{2^{i}}=a_i\times(2-\frac{1}{2^{dep}})\)。對(duì)此做前綴和即可。復(fù)雜度線性。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define gcd __gcd
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e6+5;
int n,m,num,a[maxn];
int sum[maxn],pw2[25];
il void build(int id,int l,int r,int cur){
if(l==r){
sum[l]=2*pw2[20]-pw2[20]/pw2[cur];
return ;
}
int mid=(l+r)>>1;
build(id<<1,l,mid,cur+1);
build(id<<1|1,mid+1,r,cur+1);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
read(n)read(m)read(num);
for(int i=1;i<=n;i++){
read(a[i]);
}
pw2[0]=1;
for(int i=1;i<=20;i++){
pw2[i]=pw2[i-1]*2;
}
build(1,1,n,0);
int ans=0;
for(int i=1;i<=n;i++){
ans+=a[i]*sum[i];
sum[i]+=sum[i-1];
}
int tmp=gcd(num,pw2[20]);
num/=tmp,pw2[20]/=tmp;
while(m--){
int l,r,val;
read(l)read(r)read(val);
ans+=(sum[r]-sum[l-1])*val;
printf("%lld\n",ans*num/pw2[20]);
}
return 0;
}
}
signed main(){return asbt::main();}
C. [JSOI2009] 等差數(shù)列
將原數(shù)組差分，用線段樹維護(hù)選/不選最左邊的點(diǎn)、選/不選最右邊的點(diǎn)的答案，pushup 轉(zhuǎn)移即可。
注意此處線段樹維護(hù)的是差分?jǐn)?shù)組，換句話說線段樹中長為 \(a\) 的區(qū)間在原數(shù)組中應(yīng)為 \(a+1\)。
Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,a[maxn];
struct node{
int lc,rc,num[2][2];
node(){
lc=rc=num[0][0]=num[0][1]=num[1][0]=num[1][1]=0;
}
il int*operator[](const int &x){
return num[x];
}
il node operator+(node x)const{
node res;
res.lc=lc,res.rc=x.rc;
int flag=rc==x.lc;
res[0][0]=min({num[0][1]+x[1][0]-flag,num[0][0]+x[1][0],num[0][1]+x[0][0]});
res[0][1]=min({num[0][1]+x[1][1]-flag,num[0][0]+x[1][1],num[0][1]+x[0][1]});
res[1][0]=min({num[1][1]+x[1][0]-flag,num[1][0]+x[1][0],num[1][1]+x[0][0]});
res[1][1]=min({num[1][1]+x[1][1]-flag,num[1][0]+x[1][1],num[1][1]+x[0][1]});
return res;
}
};
struct stree{
#define lid id<<1
#define rid id<<1|1
#define lc(id) tr[id].lc
#define rc(id) tr[id].rc
node tr[maxn<<2];
int tag[maxn<<2];
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void pushtag(int id,int val){
lc(id)+=val,rc(id)+=val;
tag[id]+=val;
}
il void pushdown(int id){
if(tag[id]){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=0;
}
}
il void build(int id,int l,int r){
if(l==r){
lc(id)=rc(id)=a[l];
tr[id][0][1]=tr[id][1][0]=tr[id][1][1]=1;
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,int val){
if(L>=l&&R<=r){
pushtag(id,val);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,val);
}
if(r>mid){
upd(rid,mid+1,R,l,r,val);
}
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);
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);
}
#undef lid
#undef rid
#undef lc
#undef rc
}S;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
signed main(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<n;i++){
a[i]=a[i+1]-a[i];
}
S.build(1,1,n-1);
read(m);
while(m--){
char opt;
scanf(" %c",&opt);
if(opt=='A'){
int l,r,a,b;
read(l)read(r)read(a)read(b);
if(l>1){
S.upd(1,1,n-1,l-1,l-1,a);
}
if(r>l){
S.upd(1,1,n-1,l,r-1,b);
}
if(r<n){
S.upd(1,1,n-1,r,r,-a-(r-l)*b);
}
}
else{
int l,r;
read(l)read(r);
if(l==r){
puts("1");
continue;
}
printf("%lld\n",S.query(1,1,n-1,l,r-1)[1][1]);
}
}
return 0;
}
}
signed main(){return asbt::main();}
D. [USACO04DEC] Dividing the Path G
設(shè) \(dp_i\) 表示覆蓋 \([0,i]\) 需要的最小噴灌器數(shù)。方程是好推的。
考慮怎么滿足奶牛的限制，發(fā)現(xiàn)只要滿足對(duì)于一個(gè)奶牛的區(qū)間 \([l,r]\)，\([l+1,r-1]\) 都不是某個(gè)噴水器覆蓋的區(qū)間就行了。這可以用差分 \(O(m)\) 完成。
然后暴力 dp 是 \(10^9\) 的，然而可以直接通過。以下是暴力代碼。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e3+5,maxm=1e6+5;
const int inf=0x3f3f3f3f;
int n,m,a,b,dp[maxm],flag[maxm];
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m)read(a)read(b);
for(int i=1,l,r;i<=n;i++){
read(l)read(r);
flag[l+1]++,flag[r]--;
}
for(int i=1;i<=m;i++){
flag[i]+=flag[i-1];
}
memset(dp,0x3f,sizeof dp);
dp[0]=0;
for(int i=2;i<=m;i+=2){
if(flag[i]){
continue;
}
for(int j=max(i-2*b,0);j<=i-2*a;j++){
dp[i]=min(dp[i],dp[j]+1);
}
}
printf("%d",dp[m]<inf?dp[m]:-1);
return 0;
}
}
int main(){return asbt::main();}
然而雖然這個(gè)暴力似乎無法被卡掉這個(gè)暴力的復(fù)雜度是不對(duì)的，考慮優(yōu)化。啊當(dāng)然可以線段樹優(yōu)化，但是單調(diào)隊(duì)列豈不是更好寫（時(shí)間還快）？
以下是優(yōu)化代碼：
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e3+5,maxm=1e6+5;
const int inf=0x3f3f3f3f;
int n,m,a,b,dp[maxm];
int flag[maxm],q[maxm],hd,tl;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m)read(a)read(b);
for(int i=1,l,r;i<=n;i++){
read(l)read(r);
flag[l+1]++,flag[r]--;
}
for(int i=1;i<=m;i++){
flag[i]+=flag[i-1];
}
memset(dp,0x3f,sizeof dp);
dp[0]=0;
a<<=1,b<<=1;
for(int i=a;i<=m;i+=2){
while(hd<=tl&&i-q[hd]>b){
hd++;
}
while(hd<=tl&&dp[q[tl]]>=dp[i-a]){
tl--;
}
q[++tl]=i-a;
if(!flag[i]){
dp[i]=dp[q[hd]]+1;
}
}
printf("%d",dp[m]<inf?dp[m]:-1);
return 0;
}
}
int main(){return asbt::main();}
E. Chain Queries
一個(gè)處理鏈的十分巧妙的 Trick。
我們發(fā)現(xiàn)，對(duì)于鏈中間的點(diǎn)，度數(shù)為 \(2\)，而兩端的點(diǎn)度數(shù)為 \(1\)。然而度數(shù)是不好維護(hù)的，因?yàn)橐粋€(gè)點(diǎn)改變會(huì)導(dǎo)致它的所有兒子都改變。因此我們考慮讓每個(gè)點(diǎn)都只影響它的父親。
令 \(u\) 為黑點(diǎn)，我們給 \(u\) 的權(quán)值 \(+1\)，給 \(fa_u\) 的權(quán)值 \(-1\)。于是判斷為鏈的情況只有兩種：
- 鏈從上到下。此時(shí)應(yīng)該只有一個(gè)點(diǎn)權(quán)值為 \(1\)，和一個(gè)點(diǎn)權(quán)值為 \(-1\)。
- 鏈從上向兩個(gè)方向向下。此時(shí)權(quán)值為 \(1\)，\(-1\) 的點(diǎn)都有 \(2\) 個(gè)，且那兩個(gè)為 \(1\) 的中只有一個(gè)是黑點(diǎn)，且這兩個(gè)為 \(1\) 的點(diǎn)還得相鄰。
開兩個(gè) set 維護(hù)即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=2e5+5;
int T,n,m,a[maxn],b[maxn],fa[maxn];
vector<int> e[maxn];
il void dfs(int u){
for(int v:e[u]){
if(v==fa[u]){
continue;
}
fa[v]=u;
dfs(v);
}
}
set<int> _1,__1;
template<typename T>il void upd(int u,T cal){
if(b[u]==1){
_1.erase(u);
}
else if(b[u]==-1){
__1.erase(u);
}
b[u]=cal(b[u]);
if(b[u]==1){
_1.insert(u);
}
else if(b[u]==-1){
__1.insert(u);
}
}
il int add(int x){
return x+1;
}
il int del(int x){
return x-1;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
// freopen("E.out","w",stdout);
read(T);
while(T--){
read(n)read(m);
int cnt=0;
for(int i=1;i<=n;i++){
read(a[i]);
if(a[i]){
cnt++;
}
}
for(int i=1,u,v;i<n;i++){
read(u)read(v);
e[u].pb(v),e[v].pb(u);
}
dfs(1);
for(int i=1;i<=n;i++){
if(a[i]){
b[i]--,b[fa[i]]++;
}
}
_1.clear(),__1.clear();
for(int i=0;i<=n;i++){
if(b[i]==1){
_1.insert(i);
}
else if(b[i]==-1){
__1.insert(i);
}
}
while(m--){
int u;
read(u);
if(a[u]){
upd(u,add),upd(fa[u],del);
a[u]=0,cnt--;
}
else{
upd(u,del),upd(fa[u],add);
a[u]=1,cnt++;
}
puts(cnt==1||_1.size()==1&&__1.size()==1||_1.size()==2&&__1.size()==2&&((a[*_1.begin()]&&*_1.rbegin()==fa[*_1.begin()])^(a[*_1.rbegin()]&&*_1.begin()==fa[*_1.rbegin()]))?"Yes":"No");
}
for(int i=0;i<=n;i++){
b[i]=0;
e[i].clear();
}
}
return 0;
}
}
int main(){return asbt::main();}
代碼中判斷的那個(gè) cnt==1 是可以省掉的。
F. Two Subarrays
首先考慮 dp。設(shè):
- \(dp_{i,0}\) 為到第 \(i\) 個(gè)位置還沒有開始選的答案。
- \(dp_{i,1}\) 為第 \(i\) 個(gè)位置是第一段區(qū)間的開頭或中間的答案。
- \(dp_{i,2}\) 為第 \(i\) 個(gè)位置是第一段區(qū)間的結(jié)尾或在第一、二段區(qū)間之間的答案。
- \(dp_{i.3}\) 為第 \(i\) 個(gè)位置是第二段區(qū)間的開頭或中間的答案。
- \(dp_{i,4}\) 為第 \(i\) 個(gè)位置是第二段區(qū)間的結(jié)尾或在第二段區(qū)間之后的答案。
于是有轉(zhuǎn)移方程：
\[\begin{aligned}
&dp_{i,0}=dp_{i-1,0}\\
&dp_{i,1}=\max(dp_{i-1,0}+a_i+b_i,dp_{i-1,1}+a_i)\\
&dp_{i,2}=\max(dp_{i-1,0}+a_i+2b_i,dp_{i-1,1}+a_i+b_i,dp_{i-1,2})\\
&dp_{i,3}=\max(dp_{i-1,2}+a_i+b_i,dp_{i-1,3}+a_i)\\
&dp_{i,4}=\max(dp_{i-1,2}+a_i+2b_i,dp_{i-1,3}+a_i+b_i,dp_{i-1,4})
\end{aligned}
\]
于是可以構(gòu)造出轉(zhuǎn)移矩陣。
\[\begin{bmatrix}
0&a_i+b_i&a_i+2b_i&-\infty&-\infty\\
-\infty&a_i&a_i+b_i&-\infty&-\infty\\
-\infty&-\infty&0&a_i+b_i&a_i+2b_i\\
-\infty&-\infty&-\infty&a_i&a_i+b_i\\
-\infty&-\infty&-\infty&-\infty&0
\end{bmatrix}
\]
用線段樹維護(hù)即可。矩陣的合并顯然不能是矩陣乘法，而應(yīng)該是相加取 \(\max\)。這也叫廣義矩陣乘。
時(shí)間復(fù)雜度為 \(O(mk^3\log n)\)，其中 \(k\) 為矩陣的大小，即為 \(5\)。好吧似乎比較大，甚至還有線段樹大常數(shù)，但就是過了（不知道不用快讀能不能過）。
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{
namespace cplx{bool begin;}
namespace IO{
const int bufsz=1<<20;
char ibuf[bufsz],*p1=ibuf,*p2=ibuf;
#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)
template<typename T=int>il T read(){
char ch=getchar();
bool fu=0;
while(ch<'0'||ch>'9'){
fu^=ch=='-';
ch=getchar();
}
T x=0;
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return fu?-x:x;
}
#undef getchar
char obuf[bufsz],*p3=obuf,s[50];
il int flush(){
fwrite(obuf,1,p3-obuf,stdout);
p3=obuf;
return 0;
}
#define putchar(ch) (p3==obuf+bufsz&&flush(),*p3++=(ch))
template<typename T>il void write(T x,bool typ=1){
if(x<0){
putchar('-');
x=-x;
}
int top=0;
do{
s[++top]=x%10|48;
x/=10;
}while(x);
while(top){
putchar(s[top--]);
}
putchar(typ?'\n':' ');
}
#undef putchar
}
using IO::read;
using IO::write;
const int maxn=2e5+5;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n,m;
ll a[maxn],b[maxn];
struct node{
ll mat[5][5];
il void init(){
for(int i=0;i<5;i++){
for(int j=0;j<5;j++){
mat[i][j]=-inf;
}
}
}
il ll*operator[](int x){
return mat[x];
}
il node operator+(node x)const{
node res;
res.init();
for(int i=0;i<5;i++){
for(int k=0;k<5;k++){
if(mat[i][k]<=-inf){
continue;
}
for(int j=0;j<5;j++){
if(x[k][j]<=-inf){
continue;
}
res[i][j]=max(res[i][j],mat[i][k]+x[k][j]);
}
}
}
return res;
}
}tr[maxn<<2];
il void pushup(int id){
tr[id]=tr[lid]+tr[rid];
}
il void pushtag(int id,int p){
node &t=tr[id];
t.init();
t[0][0]=0;
t[0][1]=a[p]+b[p];
t[1][1]=a[p];
t[0][2]=a[p]+2*b[p];
t[1][2]=a[p]+b[p];
t[2][2]=0;
t[2][3]=a[p]+b[p];
t[3][3]=a[p];
t[2][4]=a[p]+2*b[p];
t[3][4]=a[p]+b[p];
t[4][4]=0;
}
il void build(int id,int l,int r){
if(l==r){
pushtag(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 pos){
if(l==r){
pushtag(id,l);
return ;
}
int mid=(l+r)>>1;
if(pos<=mid){
upd(lid,l,mid,pos);
}
else{
upd(rid,mid+1,r,pos);
}
pushup(id);
}
il node query(int id,int L,int R,int l,int r){
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 query(lid,L,mid,l,r)+query(rid,mid+1,R,l,r);
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
b[i]=read();
}
build(1,1,n);
m=read();
while(m--){
int opt=read(),l=read(),r=read();
switch(opt){
case 1:{
a[l]=r;
upd(1,1,n,l);
break;
}
case 2:{
b[l]=r;
upd(1,1,n,l);
break;
}
default:{
write(query(1,1,n,l,r)[0][4]);
break;
}
}
}
IO::flush();
return 0;
}
}
int main(){return asbt::main();}
G. [SHOI2012] 魔法樹
簡單樹剖板子題，\(O(m\log^2n)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define pb push_back
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5;
int n,m,fa[maxn];
int dfn[maxn],cnt;
int sz[maxn],hes[maxn];
int top[maxn],dep[maxn];
vector<int> e[maxn];
il void dfs1(int u){
sz[u]=1;
dep[u]=dep[fa[u]]+1;
int mxs=0;
for(int v:e[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]){
dfs2(v);
}
}
}
ll sum[maxn<<2],tag[maxn<<2];
il void pushup(int id){
sum[id]=sum[lid]+sum[rid];
}
il void pushtag(int id,int l,int r,ll val){
tag[id]+=val;
sum[id]+=val*(r-l+1);
}
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 upd(int id,int L,int R,int l,int r,ll val){
if(L>=l&&R<=r){
pushtag(id,L,R,val);
return ;
}
pushdown(id,L,R);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,val);
}
if(r>mid){
upd(rid,mid+1,R,l,r,val);
}
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;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n);
for(int i=1,u,v;i<n;i++){
read(u)read(v);
fa[v]=u,e[u].pb(v);
}
dfs1(0),dfs2(0);
read(m);
while(m--){
char opt;
scanf(" %c",&opt);
if(opt=='A'){
int u,v;
ll val;
read(u)read(v)read(val);
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
upd(1,1,n,dfn[top[u]],dfn[u],val);
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
upd(1,1,n,dfn[u],dfn[v],val);
}
else{
int u;
read(u);
printf("%lld\n",query(1,1,n,dfn[u],dfn[u]+sz[u]-1));
}
}
return 0;
}
}
int main(){return asbt::main();}
H. [SHOI2016] 隨機(jī)序列
簡單手摸后發(fā)現(xiàn)，答案就是這么一個(gè)式子：
\((3^{n-1}-3^{n-2})a_1+(3^{n-2}-3^{n-3})a_1a_2+\dots+(3^1-3^0)a_1a_2\dots a_{n-1}+a_1a_2\dots a_n\)
簡單預(yù)處理，修改時(shí)取逆元區(qū)間乘就行了。
但其實(shí)不行，因?yàn)檩斎氲氖?strong>非負(fù)數(shù)，而不是正整數(shù)，而 \(0\) 是沒逆元的。
觀察式子，發(fā)現(xiàn)從第一個(gè) \(0\) 往后的項(xiàng)就都是 \(0\) 了。因此可以用一個(gè) set 來維護(hù) \(0\) 的位置。操作時(shí)正常操作，把 \(0\) 當(dāng)成 \(1\) 就行了。查詢時(shí)只查 \(1\) 到第一個(gè) \(0\) 的位置前面。
Code>
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,mod=1e9+7;
int n,m,a[maxn],b[maxn],pw3[maxn];
int sum[maxn<<2],tag[maxn<<2];
il void pushup(int id){
sum[id]=(sum[lid]+sum[rid])%mod;
}
il void pushtag(int id,int val){
tag[id]=tag[id]*1ll*val%mod;
sum[id]=sum[id]*1ll*val%mod;
}
il void pushdown(int id){
if(tag[id]>1){
pushtag(lid,tag[id]);
pushtag(rid,tag[id]);
tag[id]=1;
}
}
il void build(int id,int l,int r){
tag[id]=1;
if(l==r){
sum[id]=a[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 l,int r,int val){
if(L>=l&&R<=r){
pushtag(id,val);
return ;
}
pushdown(id);
int mid=(L+R)>>1;
if(l<=mid){
upd(lid,L,mid,l,r,val);
}
if(r>mid){
upd(rid,mid+1,R,l,r,val);
}
pushup(id);
}
il int query(int id,int L,int R,int l,int r){
if(L>=l&&R<=r){
return sum[id];
}
pushdown(id);
int mid=(L+R)>>1,res=0;
if(l<=mid){
(res+=query(lid,L,mid,l,r))%=mod;
}
if(r>mid){
(res+=query(rid,mid+1,R,l,r))%=mod;
}
return res;
}
il void debug(int id,int l,int r){
cout<<id<<" "<<l<<" "<<r<<" "<<sum[id]<<"\n";
if(l==r){
return ;
}
pushdown(id);
int mid=(l+r)>>1;
debug(lid,l,mid);
debug(rid,mid+1,r);
}
il int qpow(int x,int y){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
set<int> zero;
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
read(n)read(m);
pw3[0]=1;
for(int i=1;i<=n;i++){
read(a[i]);
if(!a[i]){
a[i]=1;
zero.insert(i);
}
b[i]=a[i];
pw3[i]=pw3[i-1]*3ll%mod;
}
zero.insert(n+1);
for(int i=n;i;i--){
(pw3[i]+=mod-pw3[i-1])%=mod;
}
for(int i=2;i<=n;i++){
a[i]=a[i]*1ll*a[i-1]%mod;
}
for(int i=1;i<=n;i++){
a[i]=a[i]*1ll*pw3[n-i]%mod;
}
build(1,1,n);
while(m--){
int pos,val;
read(pos)read(val);
zero.erase(pos);
if(!val){
val=1,zero.insert(pos);
}
upd(1,1,n,pos,n,val*1ll*qpow(b[pos],mod-2)%mod);
b[pos]=val;
printf("%d\n",*zero.begin()==1?0:query(1,1,n,1,*zero.begin()-1));
}
return 0;
}
}
int main(){return asbt::main();}
/*
4 1
1 2 3 4
1 2
*/
浙公網(wǎng)安備 33010602011771號(hào)