线段树

Task 1

维护序列静态操作：\(1 \leq n,m\leq 10^5,-15007 \leq a_i \leq 15007\)，

• l r : 询问区间最大连续子段和，即询问$ \max\limits_{l\leq i \leq j \leq r} \sum_{k=i}^j a_k$

可以设四个标记来区间连续子段和：

• \(sum\) 维护区间和
• \(lmax\)维护紧靠区间左端的最大连续子段和
• \(rmax\)维护紧靠区间右端的最大连续子段和
• \(ret\)区间连续子段和。

分别可以作如下维护：

• \(sum_x = sum_{lson} +sum_{rson}\)
• \(lmax_x = max(lmax_{lson},sum_{lson}+lmax_{rson})\)
• \(rmax_x = max(rmax_{rson},sum_{rson}+rmax_{lson})\)
• \(ret_x = max(ret_{lson} , ret_{rson} , rmax_{lson} + lmax_{rson})\)

信息合并的时候同理。

# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=1e5+10;
struct Segment_Tree{
    int sum,lmax,rmax,ret;
}tr[N<<2];
int a[N],n;
# define ls (x<<1)
# define rs ((x<<1)+1)
# define lson (x<<1),l,mid
# define rson ((x<<1)+1),mid+1,r
# define mid ((l+r)>>1)
void build(int x,int l,int r)
{
    if (l==r) {
        tr[x].sum=tr[x].lmax=tr[x].rmax=tr[x].ret=a[l];
        return;
    }
    build(lson); build(rson);
    tr[x].sum=tr[ls].sum+tr[rs].sum;
    tr[x].lmax=max(tr[ls].lmax,tr[ls].sum+tr[rs].lmax);
    tr[x].rmax=max(tr[rs].rmax,tr[rs].sum+tr[ls].rmax);
    tr[x].ret=max(max(tr[ls].ret,tr[rs].ret),tr[ls].rmax+tr[rs].lmax);
}
Segment_Tree query(int x,int l,int r,int opl,int opr)
{
    if (opl<=l&&r<=opr) return tr[x];
    if (opr<=mid) return query(lson,opl,opr);
    if (opl>mid) return query(rson,opl,opr);
    Segment_Tree lo=query(lson,opl,mid), ro=query(rson,mid+1,opr) ,ans;
    ans.sum=lo.sum+ro.sum;
    ans.lmax=max(lo.lmax,lo.sum+ro.lmax);
    ans.rmax=max(ro.rmax,ro.sum+lo.rmax);
    ans.ret=max(max(lo.ret,ro.ret),lo.rmax+ro.lmax);
    return ans;
}
signed main()
{
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    int T; scanf("%lld",&T);
    while (T--) {
        int l,r; scanf("%lld%lld",&l,&r);
        printf("%lld\n",query(1,1,n,l,r).ret);
    }
    return 0;
}

Task 2

维护序列上两个操作：\(1 \leq n,m\leq 10^5,0 \leq a_i \leq 10^{18}\)

• 0 x y 表示 对\(i\in[x,y]\)的所有元素执行\(a_i = \sqrt{a_i}\)（下取整）
• 1 x y 表示询问\(\sum_{i=x}^y a_i\)的值。

显然一个数被开若干次根号然后取整的最终会变成0/1，而且一个数最多开10次根号就会变成0/1，又没有修改操作，所以我们只需要对区间限定开根号次数即可，由于每个区间最多开10次根号，所以时间复杂度就是\(O(10\times m \ log\ n)\)

我真的醉了，md在输入里\(x > y\)都出来了！！！

# include <cstdio>
# include <iostream>
# include <cstring>
# include <cmath>
# define max(a,b) ((a)<(b)?(b):(a))
# define min(a,b) ((a)<(b)?(a):(b))
# define int long long
using namespace std;
const int N=1e5+10;
int Lim,n,m,a[N];
struct Segment_Tree{
    int sum,cnt; 
}tr[N<<2];
# define lson ls,l,mid
# define rson rs,mid+1,r
# define mid ((l+r)>>1)
# define ls (x<<1)
# define rs (x<<1|1)
void clear()
{
    memset(tr,0,sizeof(tr));
    memset(a,0,sizeof(a));
    Lim=0;
}
void build(int x,int l,int r)
{
    if (l==r) { tr[x].sum=a[l]; tr[x].cnt=0; return;}
    build(lson); build(rson);
    tr[x].sum=tr[ls].sum+tr[rs].sum;
}
void update(int x,int l,int r,int opl,int opr)
{
    if (tr[x].cnt>=Lim) return;
    if (opl<=l&&r<=opr) tr[x].cnt++;
    if (l==r) { tr[x].sum=sqrt(tr[x].sum); return;}
    if (opl<=mid) update(lson,opl,opr);
    if (opr>mid) update(rson,opl,opr);
    tr[x].sum=tr[ls].sum+tr[rs].sum;
}
int query(int x,int l,int r,int opl,int opr)
{
    if (opl<=l&&r<=opr) return tr[x].sum;
    int ret=0;
    if (opl<=mid) ret+=query(lson,opl,opr);
    if (opr>mid) ret+=query(rson,opl,opr);
    return ret;
}
signed main()
{
    int T=0;
    while (~scanf("%lld",&n)) {
        printf("Case #%lld:\n",++T);
        int Max=0; for (int i=1;i<=n;i++) scanf("%lld",&a[i]),Max=max(Max,a[i]);
        while (Max!=0&&Max!=1) Lim++,Max=sqrt(Max);
        build(1,1,n); scanf("%lld",&m);
        for (int i=1;i<=m;i++) {
            int op,l,r; scanf("%lld%lld%lld",&op,&l,&r);
            if (l>r) swap(l,r);
            if (!op) update(1,1,n,l,r);
            else printf("%lld\n",query(1,1,n,l,r));
        } clear();
        puts("");
    }
    return 0;
}

Task 3

维护一个数据结构，支持插入一个数，删除一个数，求出所有数的中位数。 $ 1≤n≤10^4 , 1 \leq T \leq 100,0 \leq a_i \leq 10^9$

对所有数离散化，然后对值域建线段树。

插入一个数、删除一个数直接在值域线段树中到叶子节点更新。

查询操作用线段树上走，左儿子比父亲小，右儿子比父亲大，通过当前剩余排名k找到对应节点。

总复杂度$ O(Tn ?log ?n)$

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=1e4+10;
int n,tmp[N],T; queue<int>dq;
struct Segment_Tree{
    int cnt;
}tr[N<<2];
struct Qes{
    int op,x;
}q[N];
# define lson ls,l,mid
# define rson rs,mid+1,r
# define mid (l+r>>1)
# define ls (x<<1)
# define rs (x<<1|1)
void clear()
{
    memset(tr,0,sizeof(tr)); memset(q,0,sizeof(q));
    memset(tmp,0,sizeof(tmp)); 
    while (dq.size()) dq.pop();
}
void insert(int x,int l,int r,int pos)
{
    if (l==r) { tr[x].cnt++; return;}
    if (pos<=mid) insert(lson,pos);
    else insert(rson,pos);
    tr[x].cnt=tr[ls].cnt+tr[rs].cnt;
}
void erase(int x,int l,int r,int pos)
{
    if (l==r) { tr[x].cnt--; return;}
    if (pos<=mid) erase(lson,pos);
    else erase(rson,pos);
    tr[x].cnt=tr[ls].cnt+tr[rs].cnt;
}
int query(int x,int l,int r,int k)
{
    if (l==r) return l;
    if (k<=tr[ls].cnt) return query(lson,k);
    else return query(rson,k-tr[ls].cnt);
}
signed main()
{
    int num=0;
    while (~scanf("%d",&n)) {
        
        for (int i=1;i<=n;i++) {
            char s[10]; scanf("%s",s);
            if (s[0]=='i') scanf("%lld",&q[i].x),q[i].op=0,tmp[++tmp[0]]=q[i].x;
            else if (s[0]=='o') q[i].op=1;
            else q[i].op=2;
        }
        sort(tmp+1,tmp+1+tmp[0]);
        T=unique(tmp+1,tmp+1+tmp[0])-tmp-1;
        printf("Case #%lld:\n",++num);
        for (int i=1;i<=n;i++) {
            if (q[i].op==0) {
                int x=lower_bound(tmp+1,tmp+1+tmp[0],q[i].x)-tmp;
                dq.push(x); insert(1,1,T,x);
            } else if (q[i].op==1) {
                erase(1,1,T,dq.front());
                dq.pop();
            } else if (q[i].op==2) {
                int k=dq.size(); k=k/2+1;
                printf("%lld\n",tmp[query(1,1,T,k)]);
            }
        }
        clear();
    }
    return 0;
}

Task 4

对于一个已知排列\(a_i \in [1,n]\)执行下列操作：\(1\leq n,m\leq 10^5\)

• 0 l r : 将\(i\in [l,r]\)的数\(a_i\)升序排序；
• 1 l r : 将\(i\in [l,r]\)的数\(a_i\)降序排序；

最后询问，第\(q\)位置上的数是多少。

首先二分答案，对于每个答案\(Mid\)把序列中小于等于它的设为\(0\),大于它的设为\(1\).

于是我们只需要统计区间当中有多少个\(0\)，多少个\(1\)就可以完成排序了。

线段树只需要完成区间查询\(01\)个数，区间赋值\(01\)即可。

我们需要找到一个位置使得\(q\)位置上的数是1，且这个位置需要最小化。

复杂度$O(m ?log_2^2 ?n) $

# pragma GCC optimize(3)
# include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Qes{
    int op,l,r;
}q[N];
int n,m,P,a[N];
struct Segment_Tree{
    int cnt0,cnt1,l,r,tag;
    Segment_Tree() { cnt0=cnt1=l=r=tag=0;}
}tr[N<<2];
# define lson ls,l,mid
# define rson rs,mid+1,r
# define ls (x<<1)
# define rs (x<<1|1)
# define mid (l+r>>1)
void up(int x) {
    tr[x].cnt0=tr[ls].cnt0+tr[rs].cnt0;
    tr[x].cnt1=tr[ls].cnt1+tr[rs].cnt1;
}
void build(int x,int l,int r,int val) {
    tr[x].l=l; tr[x].r=r; tr[x].tag=-1;
    if (l==r) { tr[x].cnt0=(a[l]<=val); tr[x].cnt1=(a[l]>val); return;}
    build(lson,val); build(rson,val);
    up(x);
}
void down(int x) {
    if (tr[x].tag==-1) return;
    if (tr[x].tag==0) {
        tr[ls].cnt0=tr[ls].r-tr[ls].l+1; tr[ls].cnt1=0; tr[ls].tag=0;
        tr[rs].cnt0=tr[rs].r-tr[rs].l+1; tr[rs].cnt1=0; tr[rs].tag=0;
    } else {
        tr[ls].cnt1=tr[ls].r-tr[ls].l+1; tr[ls].cnt0=0; tr[ls].tag=1;
        tr[rs].cnt1=tr[rs].r-tr[rs].l+1; tr[rs].cnt0=0; tr[rs].tag=1;
    }
    tr[x].tag=-1;
}
void update(int x,int l,int r,int opl,int opr,int opx) {
    if (opl<=l&&r<=opr) {
        if (opx==0) tr[x].tag=0,tr[x].cnt1=0,tr[x].cnt0=tr[x].r-tr[x].l+1;
        if (opx==1) tr[x].tag=1,tr[x].cnt0=0,tr[x].cnt1=tr[x].r-tr[x].l+1;
        return;
    }
    if (l==r) return;
    down(x);
    if (opl<=mid) update(lson,opl,opr,opx);
    if (opr>mid) update(rson,opl,opr,opx);
    up(x);
}
Segment_Tree query(int x,int l,int r,int opl,int opr) {
    if (opl<=l&&r<=opr) return tr[x];
    down(x); Segment_Tree lo,ro,ans;
    if (opl<=mid) lo=query(lson,opl,opr);
    if (opr>mid) ro=query(rson,opl,opr);
    ans.cnt0=lo.cnt0+ro.cnt0;
    ans.cnt1=lo.cnt1+ro.cnt1;
    return ans;
}
# undef lson
# undef rson
# undef ls
# undef rs
# undef mid
inline int read()
{
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w?-X:X;
}
bool check(int Mid) {
    build(1,1,n,Mid); 
    for (int i=1;i<=m;i++) if (q[i].op==0) {
        Segment_Tree ans=query(1,1,n,q[i].l,q[i].r);
        update(1,1,n,q[i].l,q[i].l+ans.cnt0-1,0);
        update(1,1,n,q[i].l+ans.cnt0,q[i].r,1);
    } else {
        Segment_Tree ans=query(1,1,n,q[i].l,q[i].r);
        update(1,1,n,q[i].l,q[i].l+ans.cnt1-1,1);
        update(1,1,n,q[i].l+ans.cnt1,q[i].r,0);
    }
    Segment_Tree ans=query(1,1,n,P,P);
    return ans.cnt0;
}
int main() {
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<=m;i++) q[i].op=read(),q[i].l=read(),q[i].r=read();
    P=read(); int l=1,r=n,ans=-1;
    while (l<=r) { 
        int mid=(l+r)>>1;
        if (check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}

Task 5

点数为 $ N $ 的树，以点 \(1\) 为根，且树节点有 点权\(a_i\)。有 $ M $ 个 操作:

• 1 x w :把某个节点 x 的点权增加 w 。
• 2 x w :把某个节点 x 为根的子树中所有点的点权都增加 w 。
• 3 x : 询问某个节点 x 到根的路径中所有点的点权和。

对于100%的数据 $ 1 \leq N,M\leq 10^5,-10^6 \leq w,a_i \leq 10^6 $

直接上树链剖分就行了。 就是肝$ O(n \log_2^2 n) $
我没听说过什么dfs线段树

# include <cstdio>
# include <iostream>
# include <cstring>
# define int long long
# define MAXN 200005
using namespace std;
typedef long long ll;
int n,m,r,val[MAXN],b[MAXN];
struct Tree{
    ll c[MAXN];
    int lowbit(int x){ return x&(-x);}
    void update(int x,int y){
        while (x<=n){
            c[x]+=y;
            x+=lowbit(x);
        }
    }
    ll query(int x){
        ll ret=0;
        while (x>0){
            ret+=c[x];
            x-=lowbit(x);
        }
        return ret;
    }
}c1,c2;
struct Edge{
    int pre,to;
}a[2*MAXN];
int head[MAXN],tot=0;
void adde(int u,int v)
{
    a[++tot].pre=head[u];
    a[tot].to=v;
    head[u]=tot;
}
ll getsum(int l,int r)
{
    return (ll) c1.query(r)*r-c2.query(r)-(l-1)*c1.query(l-1)+c2.query(l-1);
}
int f[MAXN],dep[MAXN],son[MAXN],size[MAXN];
void dfs1(int u,int fa,int depth)
{
    f[u]=fa;dep[u]=depth;size[u]=1;
    for (int i=head[u];i;i=a[i].pre)
    {
        int v=a[i].to; if (v==fa) continue;
        dfs1(v,u,depth+1);
        size[u]+=size[v];
        if (size[son[u]]<size[v]) son[u]=v;
    }
}
int w[MAXN],cntw=0,top[MAXN],old[MAXN];
void dfs2(int u,int tp)
{
    w[u]=++cntw;top[u]=tp;
    old[cntw]=u;
    if (son[u]!=0) dfs2(son[u],tp);
    for (int i=head[u];i;i=a[i].pre)
    {
        int v=a[i].to; if (v==f[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
void change(int u,int v,int d)
{
    int f1=top[u],f2=top[v];
    while (f1!=f2){
        if (dep[f1]<dep[f2]) swap(f1,f2),swap(u,v);
        c1.update(w[f1],d);
        c1.update(w[u]+1,-d);
        c2.update(w[f1],d*(w[f1]-1));
        c2.update(w[u]+1,-d*w[u]);
        u=f[f1];
        f1=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    c1.update(w[v],d);
    c1.update(w[u]+1,-d);
    c2.update(w[v],d*(w[v]-1));
    c2.update(w[u]+1,-d*w[u]);
}
ll lca(int u,int v)
{
    int f1=top[u],f2=top[v];
    ll ret=0ll;
    while (f1!=f2){
        if (dep[f1]<dep[f2]) swap(f1,f2),swap(u,v);
        ret=ret+getsum(w[f1],w[u]);
        u=f[f1];
        f1=top[u];
    }
    if (dep[u]<dep[v]) swap(u,v);
    ret=ret+getsum(w[v],w[u]);
    return ret;
}
signed main()
{
    scanf("%lld%lld",&n,&m); r=1; 
    for (int i=1;i<=n;i++) scanf("%lld",&val[i]);
    int u,v;
    for (int i=1;i<=n-1;i++) {
        scanf("%lld%lld",&u,&v);
        adde(u,v); adde(v,u);
    }
    dfs1(r,0,0);
    dfs2(r,0);
    for (int i=1;i<=n;i++) b[i]=val[old[i]];
    for (int i=1;i<=n;i++) c1.update(i,b[i]-b[i-1]),c2.update(i,(b[i]-b[i-1])*(i-1));
    int ch,x,y,z;
    for (int i=1;i<=m;i++) {
        scanf("%lld%lld",&ch,&x);
        if (ch==1) scanf("%lld",&z),change(x,x,z);
        else if (ch==2) {
            scanf("%lld",&z);
            int l=w[x],r=w[x]+size[x]-1;
            c1.update(l,z); c1.update(r+1,-z);
            c2.update(l,z*(l-1)); c2.update(r+1,-z*r);
        } else {
             printf("%lld\n",lca(x,1));
        }
    }
    return 0;
}

Task 6

维护序列上两个操作：\(1 \leq n,m\leq 10^5,0 \leq a_i \leq 10^{18}\)

• add x 表示将\(x\)加入到集合当中
• 1 x y 表示询问\(\sum_{i=x}^y a_i\)的值。

话说这个题这么写也能过啊！

#pragma GCC optimize(3)
# include <bits/stdc++.h>
using namespace std;
vector<int>a;
int n;
char s[10];
int main(){
    scanf("%d",&n); int x;
    while (n--) {
        scanf("%s",s);
        if (s[0]=='a') cin>>x,a.insert(lower_bound(a.begin(),a.end(),x),x);
        else if (s[0]=='d') cin>>x,a.erase(lower_bound(a.begin(),a.end(),x));
        else { long long ret=0; for (int i=2;i<a.size();i+=5) ret=ret+a[i]; printf("%lld\n",ret);}
    }
    return 0;
}

Task 7

给出若干个要求，\(l_i ， r_i ， q_i\)表示\(a[l_i] \& a[l_i + 1]\& ... \& a[r_i] = q_i\)

如果存在数组\(a\)则输出一行\(YES\)然后输出一种合法的数组. 否则，输出一行\(NO\).

对于100%的数据 \(\leq n\leq 10^5 , q_i \leq 2^{30}\)

可以把每个二进制为拉出来，对每一个位分别处理

如果一个区间\(l,r\) 区间 $ and $ 值为1，那么 说明这个区间必须全部是\(1\)

所以我们直接对这个区间赋值为\(1\)即可。

然后对每个询问做一遍check，判断是否合法，即看看是\(0\)位置上的\(l,r\)是不是都是\(1\)，一旦都是1，那么就前后矛盾，输出\(NO\).

上述维护可以使用差分前缀和维护。复杂度是\(O(n \ log_2 \ n)\)

# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=1e5+10;
int n,Q,c[31][N],ans[31][N];
struct rec{ int l,r,d; }q[N];
void update(int l,int r,int d)
{
    for (int i=30;i>=0;i--)
        if (d&(1ll<<i)) c[i][l]++,c[i][r+1]--;
}
void init()
{
    for (int i=0;i<=30;i++) for (int j=1;j<=n;j++) c[i][j]=c[i][j-1]+c[i][j];
    for (int i=0;i<=30;i++) for (int j=1;j<=n;j++) c[i][j]=(c[i][j]>0);
    memcpy(ans,c,sizeof(c));
    for (int i=0;i<=30;i++) for (int j=1;j<=n;j++) c[i][j]=c[i][j-1]+c[i][j];
}
bool check(int l,int r,int d)
{
    for (int i=30;i>=0;i--)
     if ((!(d&(1ll<<i)))&&(c[i][r]-c[i][l-1]==r-l+1)) return false;
    return true;
}
signed main()
{
    scanf("%lld%lld",&n,&Q);
    for (int i=1;i<=Q;i++) {
        scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].d);
        update(q[i].l,q[i].r,q[i].d);
    }
    init();
    for (int i=1;i<=Q;i++)
        if (!check(q[i].l,q[i].r,q[i].d)) { puts("NO"); return 0; }
    puts("YES");
    for (int i=1;i<=n;i++) {
        int ret=0;
        for (int j=0;j<=30;j++) if (ans[j][i]) ret+=(1<<j);
        printf("%lld ",ret);
    }
    return 0;
}

Task 8

给出\(n\)个数字的数组\(a_i\)把其分成连续的\(k\)段，每段的价值为这一段数里不同数字的个数，问价值和最大为多少。

对于100%的数据\(n\leq 35000 , k \leq min(n,50)\)

\(f[i][j]\)表示前\(i\)个数组被分成\(j\)段最大价值和。

$ f[i][j] = \max\limits_{j-1 \leq k \leq i-1}{ f[k][j-1] + w(k+1,j) }$

其中\(w(l,r)\)表示区间\([l,r]\)不重复数的个数。

考虑优化求 $ \max\limits_{j-1 \leq k \leq i-1}{ f[k][j-1] + w(k+1,j) }$

首先外层循环枚举\(j\)，内层循环枚举\(i\) , 然后首先区间赋值为\(f[k][j-1]\)

记录每个数前一次出现的位置\(pos[i]\)对于每个数\(i\)会对\([pos[i]+1,i-1]\)产生\(1\)的贡献，直接在线段树中区间加即可。

转移可用线段树维护，复杂度为\(O(n k\ log_2 n )\)

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=1e5+10,M=55;
int a[N],w[N],pos[N],pre[N],n,k;
int f[N][M];
struct Segment_Tree{
    int tag,mx;
}tr[N<<2];
# define lson ls,l,mid
# define rson rs,mid+1,r
# define mid (l+r>>1)
# define ls (x<<1)
# define rs (x<<1|1)
void build(int x,int l,int r)
{
    tr[x].tag=0; tr[x].mx=0;
    if (l==r) { tr[x].mx=w[l]; return;}
    build(lson); build(rson);
    tr[x].mx=max(tr[ls].mx,tr[rs].mx);
}
void down(int x)
{
    if (!tr[x].tag) return;
    tr[ls].mx+=tr[x].tag; tr[rs].mx+=tr[x].tag;
    tr[ls].tag+=tr[x].tag; tr[rs].tag+=tr[x].tag;
    tr[x].tag=0;
}
void update(int x,int l,int r,int opl,int opr,int d)
{
    if (opl<=l&&r<=opr) { tr[x].tag+=d; tr[x].mx+=d; return;}
    down(x);
    if (l==r) return;
    if (opl<=mid) update(lson,opl,opr,d);
    if (opr>mid) update(rson,opl,opr,d);
    tr[x].mx=max(tr[ls].mx,tr[rs].mx);
}
int query(int x,int l,int r,int opl,int opr)
{
    if (opl<=l&&r<=opr) return tr[x].mx;
    down(x);
    int ret=0;
    if (opl<=mid) ret=max(ret,query(lson,opl,opr));
    if (opr>mid) ret=max(ret,query(rson,opl,opr));
    return ret;
}
signed main()
{
    scanf("%lld%lld",&n,&k);
    for (int i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
        pos[i]=pre[a[i]];
        pre[a[i]]=i;
    }
    for (int j=1;j<=k;j++) {
        for (int i=1;i<=n;i++) w[i]=f[i-1][j-1];
        build(1,1,n);
        for (int i=1;i<=n;i++) {
            update(1,1,n,pos[i]+1,i,1);
            f[i][j]=query(1,1,n,1,i);
        }
    }
    printf("%lld\n",f[n][k]);
    return 0;
}

Task 9

一棵含有\(n\)个节点的树，维护下列两个操作 ：

• 1 u v 表示 将 u 节点点权+v ， 其儿子节点点权-v ， 其儿子的儿子的点权 + v ... 直到叶子节点。
• 2 u 表示求出 u 节点的点权

对于100%的的数据 \(1?\leq ?n,?m?\leq 2\times 10^5\)

树上节点dfs序是连续的。我们维护一个数组\(c[u]\) 表示节点\(u\)的增量。

这个\(c[u]\)数组的处理就比较简单了，直接在树上对应的dfs序区间加即可。

但是 如果在深度奇数和偶数 不同的节点上操作，对答案贡献会相反。

如果深度是奇数记录增加量，深度是偶数记录减少量。

最终答案就是初始值加上或减去贡献。

复杂度是\(O(n \ log_2 \ n)\)

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=2e5+10;
struct rec{ int pre,to; }a[N<<1];
int L[N],R[N],c[N],v[N],head[N],dep[N];
int n,tot,cnt,m;
void adde(int u,int v)
{
    a[++tot].pre=head[u];
    a[tot].to=v;
    head[u]=tot;
}
void dfs(int u,int fa)
{
    L[u]=++cnt; dep[u]=dep[fa]+1;
    for (int i=head[u];i;i=a[i].pre) {
        int v=a[i].to; if (v==fa) continue;
        dfs(v,u);
    }
    R[u]=cnt;
}
# define lowbit(x) (x&(-x))
void update(int x,int y){for (;x<=n;x+=lowbit(x)) c[x]+=y;}
int query(int x){int ret=0; for (;x;x-=lowbit(x)) ret+=c[x]; return ret;}
void modify(int l,int r,int d){update(l,d); update(r+1,-d);}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&v[i]);
    for (int i=1;i<n;i++) {
        int u,v; scanf("%lld%lld",&u,&v);
        adde(u,v); adde(v,u);
    }
    dfs(1,0);
    for (int i=1;i<=m;i++) {
        int op,x; scanf("%lld%lld",&op,&x);
        if (op==1) {
            int d; scanf("%lld",&d);
            if (dep[x]&1) modify(L[x],R[x],d);
            else modify(L[x],R[x],-d);
        } else {
            if (dep[x]&1) printf("%lld\n",v[x]+query(L[x]));
            else printf("%lld\n",v[x]-query(L[x]));
        }
    }
    return 0;
}

线段树习题 总结

原文：https://www.cnblogs.com/ljc20020730/p/11291465.html