这是一个做题记录。
洛谷P1725 琪露诺
2023.8.5
标签：动态规划、单调队列。
一道动态规划题，先考虑暴力一点的做法：
设 \(dp[i]\) 表示跳到第 \(i\) 个位置时所能获得的最大冰冻指数。那么 \(i\) 位置的状态可以从区间 \([i-L,i-R]\) 转移过来。
转移方程：$dp[i] = max(dp[j]) + a[i] $ ,其中 \(j\in [i-L,i-R]\) 。
时间复杂度为 \(O(n^2)\)
暴力DP在本题的预计得分为60分，然而在开了氧气优化的情况下能直接过掉本题。
考虑一个时间复杂度更优的做法：
每次转移需要求一个区间的最大值，而每个区间都是从上一个区间右移一个单位得到的，因此可以使用单调队列优化。
题目存在部分细节需要注意：
\(a[i]\) 可能为负数。当 \(i+r>=n\) 时才能跳到对岸，答案应在 \([n-r,n]\) 范围里选取。
暴力代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,dp[10211021],vis[10231311],L,R,ans=-0x7ffffff,w=0;
signed main(){
cin>>n>>L>>R;
memset(dp,-0x3f,sizeof(dp));
for (int i=0;i<=n;++i) {
cin>>vis[i];
}
dp[0]=0;
for (int i=L;i<=n+R-1;++i) {
for (int j=max(w,i-R);j<=i-L;++j) {
dp[i]=max(dp[i],dp[j]+vis[i]);
}
//cout<<dp[i]<<endl;
if (i>=n) ans=max(ans,dp[i]);
}
cout<<ans;
return 0;
}
单调队列优化代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2023;
int n,m,l,r,a[N],dp[N],tail,q[N],p[N],ans=-1e9;
signed main(){
cin>>n>>l>>r;
for (int i=0;i<=n;++i) {
cin>>a[i];
}
memset(dp,~0x3f,sizeof(dp));
int head=tail=0,len=r-l+1;
dp[0]=0;
for (int i=0;i<=n-l;++i) {
while(head<=tail&&q[tail]<dp[i]) --tail;
q[++tail]=dp[i]; p[tail]=i;
while(head<=tail && p[head]<i-len+1) ++head;
dp[i+l]=q[head]+a[i+l];
if (i+r>=n) ans=max(ans,dp[i+l]);
//ans=max(ans,dp[i+l]);
}
cout<<ans;
return 0;
}
CF383C Propagating tree
2023.8.5
标签：树链剖分
题目需要我们对一个节点加上一个值，然后修改这个点的子树内各个点的值，从这个点到根节点每层 \(+val\) 和 \(-val\) 交替进行。以及查询某点的子树权值和。
需要支持操作：子树修改，查询子树权值和。
子树修改和查询子树权值和不难想到树剖，但怎么在线段树上修改区间就成了问题。
不难发现一个节点的子树内每一层改变权值的符号相同(同一层一定都是加上一个数或者同一层都时减去一个数)。因此我们可以通过每个节点的深度的奇偶性判断这个数是加上这个值还是减去这个值。
即在 \(x\) 子树内，深度与\(x\)深度的奇偶性相同的点加上 \(val\),奇偶性不同的点减去 \(val\) 。
然而这样懒标记不好合并，如果选择舍弃懒标记直接单点修改的话，时间复杂度就会退化成 \(O(n^2 logn)\) 。
一个比较神奇的思路是：
修改时只考虑子树根节点深度的奇偶性，子树根节点深度为奇数就对整颗子树 \(+val\),子树根节点深度为偶数时就对整颗子树 \(-val\)。
查询时根据每个节点的奇偶性，加上或减去对应的值。（可以放在 push_down 里实现)。
这个题目不需要查询区间，因此树状数组更优秀一些，不过我还是更喜欢写线段树。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
char ch=getchar(); int x=0,f=0;
for (;!isdigit(ch);ch=getchar()) f|=(ch=='-');
for (;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
return f?-x:x;
}
void print(int x) {
if (x<0) { putchar('-'); x=-x; }
if (x>9) print(x/10);
putchar(x%10+48);
}
const int N=2e5+2023;
int n,m,a[N],head[N<<1],cnt;
int tot,dfn[N],pre[N],top[N],fa[N],son[N],dep[N],size[N];
struct node{
int next,to,w;
}e[N<<1];
void add(int u,int v) {
e[++cnt].next=head[u];
e[cnt].to=v;
head[u]=cnt;
}
namespace ss{
#define lson pos<<1
#define rson pos<<1|1
struct node{
int sum,len,lazy,dep;
}tree[N<<2];
void build(int pos,int l,int r) {
tree[pos].len=r-l+1;
if (l==r) {
tree[pos].sum=a[pre[l]];
tree[pos].dep=dep[pre[l]];
return ;
}
int mid=l+r>>1;
build(lson,l,mid); build(rson,mid+1,r);
}
void push_down(int pos){
if (!tree[pos].lazy) return ;
if (tree[lson].dep!=0) {
if (tree[lson].dep%2==1) tree[lson].sum+=tree[pos].lazy;
else tree[lson].sum-=tree[pos].lazy;
}
if (tree[rson].dep!=0) {
if (tree[rson].dep%2==1) tree[rson].sum+=tree[pos].lazy;
else tree[rson].sum-=tree[pos].lazy;
}
tree[lson].lazy+=tree[pos].lazy;
tree[rson].lazy+=tree[pos].lazy;
tree[pos].lazy=0;
}
void change(int pos,int l,int r,int L,int R,int k){
if (l>=L && r<=R) {
tree[pos].lazy+=k;
if (tree[pos].dep!=0) {
if (tree[pos].dep%2) tree[pos].sum+=k;
else tree[pos].sum-=k;
}
return ;
}
int mid=l+r>>1; push_down(pos);
if(L<=mid) change(lson,l,mid,L,R,k);
if(R>mid) change(rson,mid+1,r,L,R,k);
}
int query(int pos,int l,int r,int k) {
if (l==r) return tree[pos].sum;
int mid=l+r>>1; push_down(pos);
if (k<=mid) return query(lson,l,mid,k);
else return query(rson,mid+1,r,k);
}
}
namespace sp{
void dfs1(int now,int Fa) {
size[now]=1; fa[now]=Fa; dep[now]=dep[Fa]+1;
for (int i=head[now];i;i=e[i].next) {
if (e[i].to==Fa) continue;
dfs1(e[i].to,now);
size[now]+=size[e[i].to];
if (size[son[now]]<size[e[i].to]) son[now]=e[i].to;
}
}
void dfs2(int now,int Top) {
dfn[now]=++tot; pre[tot]=now; top[now]=Top;
if(son[now]) dfs2(son[now],Top);
for (int i=head[now];i;i=e[i].next) {
if (e[i].to==son[now]||e[i].to==fa[now]) continue;
dfs2(e[i].to,e[i].to);
}
}
}
signed main(){
n=read(); m=read();
for (int i=1;i<=n;++i) {
a[i]=read();
}
for (int i=1;i<n;++i) {
int x=read(),y=read();
add(x,y); add(y,x);
}
sp::dfs1(1,0); sp::dfs2(1,1); ss::build(1,1,n);
int op,x,y;
for (int i=1;i<=m;++i) {
op=read();
if (op==1) {
x=read(),y=read();
if (dep[x]%2) ss::change(1,1,n,dfn[x],dfn[x]+size[x]-1,y);
else ss::change(1,1,n,dfn[x],dfn[x]+size[x]-1,-y);
//cout<<" "<<ss::tree[1].sum<<endl;
}
if (op==2) {
x=read();
print(ss::query(1,1,n,dfn[x]));
putchar('\n');
}
}
return 0;
}