D-数据结构

不会出题人的妙妙均摊，更新一个比较不用动脑子的线段树写法

sort排序后更新操作不会改变数组的有序性。最初的 $sum$ 是已知的，每次更新操作只需要计算出有多少数字被更改就可以知道当前的答案。

此时考虑线段树节点存储信息，区间内奇数个数，偶数个数决定被修改的有多少。每次更新都是值域范围的更新，要实现在线段树上查找就要维护区间的最大值和最小值，由于数组一直都是有序的，这两个值就很好维护。（如果不在线段树上查找，用二分求出值域对应的下标会被卡）。

接下来考虑区间更新怎么标记，该区间的最后一次更新操作决定了这个区间全是偶数还是全是奇数。再考虑维护减少的值，可以发现减少的值就是更新操作的段数，比如 $010110111$ 如果原值的奇偶性和开始的操作相同那么减少的值就是6次，否则就是5次。这就需要记录第一次操作的情况和有多少段数。其他就是线段树的板子了。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

const int N=5e5+9,inf=1e18;

int a[N];

struct node{
    int sum,max,len,min;
}tr[N<<2];
int n,q;
node mer(node a,node b)
{
    node res;
    if(a.len==0)
    {
        return b;
    }
    res=b;
    res.len+=a.len;
    res.sum+=a.sum;
    res.min=a.min;
    return res;
}
int fi[N<<2],laz[N<<2],la[N<<2];
int num1,num2;
void build(int rt,int l,int r)
{
    fi[rt]=-1,la[rt]=-1;
    if(l==r)
    {
        tr[rt]={a[l]%2,a[l],1,a[l]};
        return;
    }
    else
    {
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        tr[rt]=mer(tr[rt<<1],tr[rt<<1|1]);
        return;
    }
}
void change(int rt,int x,int len)
{
    if(!la[x])tr[rt].sum=len;
    else tr[rt].sum=0;
    if((tr[rt].max%2)==fi[x])tr[rt].max-=laz[x]+1;
    else tr[rt].max-=laz[x];
    if((tr[rt].min%2)==fi[x])tr[rt].min-=laz[x]+1;
    else tr[rt].min-=laz[x];
    if(la[rt]==-1)fi[rt]=fi[x];
    if(fi[x]!=la[rt]&&la[rt]!=-1)laz[rt]++;
    laz[rt]+=laz[x],la[rt]=la[x];
}
void pushdown(int rt,int l,int r)
{
    if(la[rt]!=-1)
    {
        int mid=l+r>>1;
        change(rt<<1,rt,mid-l+1);
        change(rt<<1|1,rt,r-mid);
        fi[rt]=-1,la[rt]=-1,laz[rt]=0;
    }
}
node query(int rt,int l,int r,int L,int R,int c)
{
    if(l>r)
    {
        return {0,0,0,0};
    }
    if(tr[rt].min>num2)
    {
        return {0,0,0,0};
    }
    if(tr[rt].max<num1)
    {
        return {0,0,0,0};
    }
    if(num1<=tr[rt].min&&tr[rt].max<=num2)
    {
        node res=tr[rt];
        if(!c)tr[rt].sum=r-l+1;
        else tr[rt].sum=0;
        if(c==(tr[rt].max%2))tr[rt].max-=1;
        if(c==(tr[rt].min%2))tr[rt].min-=1;
        if(fi[rt]==-1)fi[rt]=c;
        if(la[rt]!=-1&&c!=la[rt])laz[rt]+=1;
        la[rt]=c;
        return res;
    }
    else
    {
        node res={0,0,0,0};
        int mid=l+r>>1;
        pushdown(rt,l,r);
        res=mer(res,query(rt<<1,l,mid,L,R,c));
        res=mer(res,query(rt<<1|1,mid+1,r,L,R,c));
        tr[rt]=mer(tr[rt<<1],tr[rt<<1|1]);
        return res;
    }
}
void solve() {
    std::cin>>n>>q;
    i64 sum=0,ans=0;
    for(int i=1;i<=n;i++)std::cin>>a[i],sum+=a[i];
    std::sort(a+1,a+n+1);
    build(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int c;std::cin>>num1>>num2>>c;
         auto it=query(1,1,n,1,n,c);
        if(c==0)sum-=(it.len-it.sum);
        else sum-=it.sum;
        ans^=(i*sum);
    }
    std::cout<<ans;
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1;
 //   std::cin >> t;
    while (t--) {
        solve();
    }
}

题解

D-数据结构