Codeforces 903G 巧妙的线段树

时间：2022-12-03 22:42:09

思路：

巧妙的线段树

想方法将网络流往数据结构方向转化

http://www.cnblogs.com/yyf0309/p/8724558.html

//By SiriusRen

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

int n,m,q,X[N],y[N],tmp=,xx,yy;

ll tree[N<<],lazy[N<<],x[N];

struct Node{int from,to,wei;}node[N];

bool operator<(Node a,Node b){return a.from<b.from;}

void insert(int l,int r,int pos,int L,int R,ll wei){

    if(l>=L&&r<=R){tree[pos]+=wei;lazy[pos]+=wei;return;}

    int mid=(l+r)>>,lson=pos<<,rson=pos<<|;

    if(mid<L)insert(mid+,r,rson,L,R,wei);

    else if(mid>=R)insert(l,mid,lson,L,R,wei);

    else insert(l,mid,lson,L,R,wei),insert(mid+,r,rson,L,R,wei);

    tree[pos]=min(tree[lson],tree[rson])+lazy[pos];

}

int main(){

    scanf("%d%d%d",&n,&m,&q);

    for(int i=;i<=n;i++)scanf("%lld%d",&x[i-],&y[i]);

    for(int i=;i<=m;i++)scanf("%d%d%d",&node[i].from,&node[i].to,&node[i].wei);

    for(int i=;i<=n;i++)insert(,n,,i,i,y[i]);

    sort(node+,node++m);

    for(int i=;i<=n;i++){

        for(;tmp<=m&&node[tmp].from<=i;tmp++)

            insert(,n,,,node[tmp].to,node[tmp].wei);

        X[i]=x[i],x[i]+=tree[];

    }memset(tree,,sizeof(tree)),memset(lazy,,sizeof(lazy));

    for(int i=;i<=n;i++)insert(,n,,i,i,x[i]);

    printf("%lld\n",tree[]);

    while(q--){

        scanf("%d%d",&xx,&yy);

        insert(,n,,xx,xx,yy-X[xx]),X[xx]=yy;

        printf("%lld\n",tree[]);

    }

}

相关文章