codeforces 1180E Serge and Dining Room 线段树

题目大意：

　　给出a序列和b序列，a序列为各种食物的价格，b序列为一列排着队的小朋友拥有的钱，小朋友依次购买食物，每个人都买自己能买的起的最贵的食物，买不起就离开队伍。给出q次操作，操作1是修改食物的价格，操作2是修改小朋友的钱，每次操作后询问当小朋友买完之后，能买到的最贵的食物的价格是多少，没有食物了就输出-1.

思路：

　　首先，小朋友的顺序对最终答案没有任何影响，因为如果两个小朋友能买两个东西，这两个小朋友无论怎么换，都是能买的了的。

　　其次，对于一个价格为x的物品，如果有一个钱大于等于x的小朋友，就可以买走这个物品。如果我们把价格想象成一条数轴，那么物品就是1，小朋友就是-1，价格或者钱就是坐标轴的位置，这道题就转化成了求最大的后缀和大于等于1的下标。

　　最后，我们用线段树来维护这个值，注意用线段树维护最大后缀和时，在查询时要注意后面的区间的影响。

#include<bits/stdc++.h>

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

const int maxn=;

int n,m,q;

int sum[maxn<<],maxx[maxn<<];

int a[maxn],b[maxn];

void update(int o,int l,int r,int p,int val){

    if(l==r){

        sum[o]+=val;

        maxx[o]+=val;

        return;

    }

    int mid=(l+r)>>;

    if(p<=mid)update(o<<,l,mid,p,val);

    else update(o<<|,mid+,r,p,val);

    sum[o]=sum[o<<]+sum[o<<|];

    maxx[o]=max(maxx[o<<|],maxx[o<<]+sum[o<<|]);

    //这里的每一个maxx，都是对应的 区间最大后缀和  但不是整根数轴的最大后缀和。

}

struct node{

    int max,sum;

};

int query(int o,int l,int r,node tep){

    if(l==r){

        return l;

    }

    int mid=(l+r)>>;

    node tep2;

    tep2.sum=tep.sum+sum[o<<|];

    tep2.max=maxx[o<<|]+tep.sum;//将 标号为o这段区间的后面一段（o+1）的影响合并到o区间中

    if(tep2.max>){

        return query(o<<|,mid+,r,tep);

    }

    else {

        return query(o<<,l,mid,tep2);

    }

}

int main(){

    while(cin>>n>>m){

        clr(sum,),clr(maxx,);

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

            scanf("%d",&a[i]);

            update(,,maxn-,a[i],);

        }

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

            scanf("%d",&b[i]);

            update(,,maxn-,b[i],-);

        }

        cin>>q;

        while(q--){

            int op,pos,val;

            scanf("%d%d%d",&op,&pos,&val);

            if(op==){

                update(,,maxn-,a[pos],-);

                update(,,maxn-,a[pos]=val,);

            }else{

                update(,,maxn-,b[pos],);

                update(,,maxn-,b[pos]=val,-);

            }

            if(maxx[]<=)puts("-1");

            else printf("%d\n",query(,,maxn-,{,}));

        }

    }

}

巴特西

codeforces 1180E Serge and Dining Room 线段树

最新文章

热门文章