题解：P16497 东风归故里，托此报微酬

I_do_Cpp · 2026-05-20 17:40:14 · 题解

题目解析

竞选最唐做法。

下文中 (x,y) 表示 x 到 y 左右都开的区间而不是二元组。

首先设 pre_i 是 \max(a_1,a_2,\dots,a_n) 的值，显然当且仅当 pre_i=a_i 时，a_i 是「春风拂面」的。

不妨设修改了 i 位置，修改后的答案是 a_j。首先，对于 pre_i>a_i 的情况，忽略此操作即可。对于其他情况，容易发现每次修改的时候，若存在 r \ge l,j >i 使得 a_j \ge a_i 的最左的 r，那么 (i,r) 的区间的点都要因为 a_i 取消「春风拂面」的状态。特别的，若所有数字都比 a_i 小，令 r \leftarrow n+1。

然后又注意到在 r 之前，pre_i < a_i，且 r 之后，pre_i \ge a_i，这是前缀最大值的基本性质。

开两颗线段树分别维护每个点是否「春风拂面」以及 pre 即可。

代码细节太多了。具体看注释。

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define getchar_unlocked getchar
#define putchar_unlocked putchar
inline void read(int& x)
{
    x=0;
    char ch=getchar_unlocked();
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') flag=1;
        ch=getchar_unlocked();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar_unlocked();
    }
    if(flag) x=-x;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar_unlocked('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar_unlocked(x%10+'0');
}

//此版本默认求和，有需要请修改。
class SGT1 
{
    private:
        vector<int> tag;
        inline int dosth(int a,int b) 
        {
            return a+b;
        }
        inline int lft(int p)  //左孩子
        {
            return (p<<1);
        }
        inline int rit(int p)  //有孩子
        {
            return ((p<<1)|1);
        }
        void addtag(int p,int l,int r,int x) //加标记
        {
            tag[p]=x;
            t[p]=x*(r-l+1);//根据实际情况更改！！！
        }
        void pd(int p,int l,int r) //向下更新
        {
            if(tag[p]==-1) return; 
            int mid=(l+r)/2;
            addtag(lft(p),l,mid,tag[p]);
            addtag(rit(p),mid+1,r,tag[p]);
            tag[p]=-1;
        }
        void up(int p)
        {
            t[p]=dosth(t[lft(p)],t[rit(p)]);
        }
    int t[800005]={0};
    public:
        SGT1(int sz)
        {

            tag.resize(sz*4+4,-1);
        }
        void update(int p,int l,int r,int x,int y,int k) //修改
        {
            if(x<=l && r<=y)
            {
                addtag(p,l,r,k);
                return;
            }
            if(l==r) return;
            pd(p,l,r);
            int mid=(l+r)>>1;
            if(x<=mid) update(lft(p),l,mid,x,y,k);
            if(mid<y) update(rit(p),mid+1,r,x,y,k);
            up(p);
        }
        int query(int p,int l,int r,int x,int y) //查询
        {
            if(x<=l && r<=y)
            {
                return t[p];
            }
            if(l==r) return 0;
            pd(p,l,r);
            int mid=(l+r)>>1,ans=0;//必要时更改ans
            if(x<=mid) ans=dosth(ans,query(lft(p),l,mid,x,y));
            if(mid<y) ans=dosth(ans,query(rit(p),mid+1,r,x,y));
            return ans;
        }
};
//此版本默认求和，有需要请修改。

class SGT2
{
    private:
        inline int dosth(int a,int b) 
        {
            return max(a,b);//根据实际情况更改！！！
        }
        inline int lft(int p)  //左孩子
        {
            return (p<<1);
        }
        inline int rit(int p)  //右孩子
        {
            return ((p<<1)|1);
        }
        void addtag(int p,int l,int r,int x) //加标记
        {
            tag[p]=x;
            t[p]=x;
        }
        void pd(int p,int l,int r) //向下更新
        {
            if(!tag[p]) return; 
            int mid=(l+r)/2;
            addtag(lft(p),l,mid,tag[p]);
            addtag(rit(p),mid+1,r,tag[p]);
            tag[p]=0;
        }
        void up(int p)
        {
            t[p]=dosth(t[lft(p)],t[rit(p)]);
        }
    public:
                int a[200004]={0};
            int t[800004]={0};
            int tag[8000004]={0};
        SGT2(int sz)
        {

        }
        void build(int p,int l,int r) //建树
        {
            if(l==r)
            {

                t[p]=a[l];
                return;
            }
            int mid=(l+r)>>1;
            build(lft(p),l,mid);
            build(rit(p),mid+1,r);
            up(p);
        }
        void update(int p,int l,int r,int x,int y,int k) //修改
        {
            if(x<=l && r<=y)
            {
                addtag(p,l,r,k);
                return;
            }
            if(l==r) return;
            pd(p,l,r);
            int mid=(l+r)>>1;
            if(x<=mid) update(lft(p),l,mid,x,y,k);
            if(mid<y) update(rit(p),mid+1,r,x,y,k);
            up(p);
        }
        int query(int p,int l,int r,int x) //查询
        {

                if(t[p]<x) return r+1; //特判：x如果是全局最大
            if(l==r) return l;//返回位置
            pd(p,l,r);//这个不能放在前面！要后更新！我调试了 1 天！
            int mid=(l+r)>>1,ans=0;
            if(t[lft(p)]>=x) //在线段树上二分，左边有符合的去左边，否则去右边
            {

                return query(lft(p),l,mid,x);
            }
            else 
            {
                return query(rit(p),mid+1,r,x); 
            }
        }
        int qwq(int p,int l,int r,int x)
        {
            if(l==r)
            {
                return t[p];
            }
            pd(p,l,r);
            int mid=l+r>>1;
            if(x<=mid) return qwq(p*2,l,mid,x);
            else return qwq(p*2+1,mid+1,r,x);
        }
};
SGT1 t1(200005);//维护每个点是否春风拂面
SGT2 t2(200005);//维护每个点的pre
int a[200005];
int pre[200005]; 
signed main()
{
    int n,q,c,last=0;
    cin>>n>>q>>c;
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        pre[i]=max(a[i],pre[i-1]);
        if(pre[i]==a[i]) t1.update(1,1,n,i,i,1);
        t2.a[i]=pre[i]; 
    }
    t2.build(1,1,n);

    for(int i=1;i<=q;i++)
    {
        int p,x;
        read(p);read(x);
        p^=c*(last%3);
        a[p]+=x;
        int l=p,r=t2.query(1,1,n,a[p])-1;

if(l>r)
{
    //这里不一定 pre_i > a_i。这个 query 有一个大缺陷，就是如果 a_i 是最大值，但是序列中有一样的值，代码会搜到这个一样的值。
    int mx_p=t2.qwq(1,1,n,p);
    if(a[p]==mx_p) t1.update(1,1,n,p,p,1); //取特判这种情况
}
else
{
        t2.update(1,1,n,l,r,a[p]);
        t1.update(1,1,n,l,r,0);
        t1.update(1,1,n,p,p,1);
    }

        last=t1.query(1,1,n,1,n);

        write(last);
        putchar('\n');
    }
    return 0;
}