题目大意： 给定n个点排成一排，每个点有一个点权，有m次修改，每次改变某个点的点权并将最大点独立集计入答案，输出最终的答案 其中 n≤40000 , m≤50000 n ≤ 40000 , m ≤ 50000
QWQ说实话，一开始看这个题，没啥思路呀
后来看了题解才知道是线段树
我们考虑对一个区间，我们只需要关心左右节点是否取，就可以从小的区间更新大区间。 从而实现线段树的区间合并了
QWQ我们定义 f[i].both f [ i ] . b o t h 表示左右边界都取 f[i].left f [ i ] . l e f t 表示只取左边界 f[i].right f [ i ] . r i g h t 表示只取右边界 f[i].neither f [ i ] . n e i t h e r 表示左右边界都不取
对于每种情况，我们分开讨论
首先定义 l=2∗root,r=2∗root+1 l = 2 ∗ r o o t , r = 2 ∗ r o o t + 1 对于 f[root].both f [ r o o t ] . b o t h f[root].both=max(f[l].left+max(f[r].both,f[r].right),f[l].both+f[r].right); f [ r o o t ] . b o t h = m a x ( f [ l ] . l e f t + m a x ( f [ r ] . b o t h , f [ r ] . r i g h t ) , f [ l ] . b o t h + f [ r ] . r i g h t ) ; 也就是如果左边只取左，右边可以都取或者只取右 如果左边都取，那么右边只能取右了（因为中间的左右区间的交界处也是不能同时取到的）
对于 f[root].right,f[root].left f [ r o o t ] . r i g h t , f [ r o o t ] . l e f t
f[root].left=max(f[l].left+max(f[r].neither,f[r].left),f[l].both+f[r].neither); f [ r o o t ] . l e f t = m a x ( f [ l ] . l e f t + m a x ( f [ r ] . n e i t h e r , f [ r ] . l e f t ) , f [ l ] . b o t h + f [ r ] . n e i t h e r ) ; f[root].right=max(f[l].neither+max(f[r].right,f[r].both),f[l].right+f[r].right); f [ r o o t ] . r i g h t = m a x ( f [ l ] . n e i t h e r + m a x ( f [ r ] . r i g h t , f [ r ] . b o t h ) , f [ l ] . r i g h t + f [ r ] . r i g h t ) ;
同样的方法，处理一下
而对于 f[root].neither f [ r o o t ] . n e i t h e r
f[root].neither=max(max(f[l].neither+f[r].neither,f[l].right+f[r].neither),f[r].left+f[l].neither) f [ r o o t ] . n e i t h e r = m a x ( m a x ( f [ l ] . n e i t h e r + f [ r ] . n e i t h e r , f [ l ] . r i g h t + f [ r ] . n e i t h e r ) , f [ r ] . l e f t + f [ l ] . n e i t h e r )
然后考虑更新的部分话
将一个点权修改也就是重新更新那个节点的 f[root].both f [ r o o t ] . b o t h ，然后将其他的清零。 最后更新就行
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> #include<queue> #include<map> #include<vector> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } const int maxn = 40010; struct Node{ int left,right,both,neither; }; Node f[4*maxn]; int n,a[maxn]; int m; long long ans; void up(int root) { int l = 2*root,r=2*root+1; f[root].both=max(f[l].left+max(f[r].both,f[r].right),f[l].both+f[r].right); f[root].left=max(f[l].left+max(f[r].neither,f[r].left),f[l].both+f[r].neither); f[root].right=max(f[l].neither+max(f[r].right,f[r].both),f[l].right+f[r].right); f[root].neither=max(max(f[l].neither+f[r].neither,f[l].right+f[r].neither),f[r].left+f[l].neither); } void build(int root,int l,int r) { if (l==r) { f[root].left=f[root].right=f[root].neither=0; f[root].both=a[l]; return; } int mid = (l+r) >> 1; build(2*root,l,mid); build(2*root+1,mid+1,r); up(root); } void update(int root,int l,int r,int x,int p) { if (l==r) { f[root].left=f[root].right=f[root].neither=0; f[root].both=p; return; } int mid =(l+r) >> 1; if (x<=mid) update(2*root,l,mid,x,p); if (x>mid) update(2*root+1,mid+1,r,x,p); up(root); } int main() { n=read();m=read(); for (int i=1;i<=n;i++) a[i]=read(); build(1,1,n); for (int i=1;i<=m;i++) { int day,x; day=read(),x=read(); update(1,1,n,day,x); long long tmp=max(f[1].left,max(f[1].right,max(f[1].both,f[1].neither))); ans+=tmp; } cout<<ans<<endl; return 0; }