题解 P7770 丑国传说 · 丑国旅游（En:Travel To The Ugly）

· · 题解

传送门，是划水时口胡的一道大水题

前置知识：

可持久化线段树。

题意：

为了简洁，设 f_{x,i}=|x-a_i|\times|x-a_{i+1}|。

分析：

这题题面看起来就像线段树，但注意到对于每个 x，f_{x,i} 都不相同，我们也开不下 10^9 棵线段树，所以暂时并不行。（对于 10\% 的 x\le10 的数据，这一方法就非常可行）

不过离散化后，我们可能只需要开 3\times10^5 棵树，这提示我们往可持久化线段树的方向思考。

根据绝对值的定义，有：

|x-a|=\begin{cases}x-a&x\ge a\\-x+a &x<a\end{cases}

那么：

f_{x,i}=\begin{cases}x^2-(a_i+a_{i+1})x+a_ia_{i+1}&x\ge\max(a_i,a_{i+1})\text{ 或 }x<\min(a_i,a_{i+1})\\-x^2+(a_i+a_{i+1})x-a_ia_{i+1}&\min(a_i,a_{i+1})\le x<\max(a_i,a_{i+1})\end{cases}

只要 x 与 a_i，a_{i+1} 的关系确定后，我们就可以选择上述式子来求出答案，而不需要确定 x 的具体值。

具体地，假设 f_{x,i}=bx^2+cx+d，则有 \sum f_{x,i}=x^2\sum b+x\sum c+\sum d，可以用线段树维护 \sum b，\sum c 和 \sum d，这样线段树就与 x 的具体值无关了。

注意到当 x 增大的过程中，x 与 a_i 的关系最多改变一次（从 x\le a_i 到 x>a_i），并且总是当 x 超过 a_i 的时候，f_{x,i}，f_{x,i-1} 会改变。因此对于每个 a_i 建一棵线段树，并使用可持久化线段树维护这 n 棵树。每次 x 超过 a_i 时，在上一棵树的基础上修改 f_{x,i-1} 和 f_{x,i}，就可以解决问题了。

思路：

  1. 对每一个 a_i 开一棵线段树，并使用可持久化线段树维护。

  2. 对每个查询二分查找应该查询哪一棵线段树，直接查询即可。

技巧不多，直接上代码。

#include <bits/stdc++.h>
#define rep(i, l, r) for(register int i=l; i<=r; ++i)
#define rrep(i, r, l) for(register int i=r; i>=l; --i)
#define lfor(i, x) for(int i=head[x]; i; i=nxt[i])
#define ll long long
using namespace std;
inline ll read() {
    ll ret=0, k=1; char c; do if((c=getchar())=='-') k=-1; while(c<'0' || c>'9');
    while(c>='0' && c<='9') ret=(ret<<1)+(ret<<3)+(c^48), c=getchar(); return k*ret;
}
const int mN=3e5+100, mS=42*mN, mod=1e9+7;
int n, m, a[mN];
int ork, rk[mN];
int oe, head[mN], ver[mN], nxt[mN];
inline void add(int x, int y) {nxt[++oe]=head[x], ver[oe]=y, head[x]=oe;}

namespace Segment_Tree {
#define lc tree[p].son[0]
#define rc tree[p].son[1]
    int on, rt[mN];
    struct node {int son[2]; int b, c, d;} tree[mS];    //b c d 就是题解中提到的三个系数 
    inline void push_up(int p) {
        tree[p].b=(tree[lc].b+tree[rc].b)%mod;
        tree[p].c=(tree[lc].c+tree[rc].c)%mod;
        tree[p].d=(tree[lc].d+tree[rc].d)%mod;
    }
    void build(int &p, int l, int r) {
        p=++on;
        if(l==r) {
            if(1<=l && l<=n) tree[p].b=1, tree[p].c=(-a[l]-a[l+1])%mod, tree[p].d=(ll) a[l]*a[l+1]%mod;
            else tree[p].b=tree[p].c=tree[p].d=0;
        } else build(lc, l, l+r>>1), build(rc, (l+r>>1)+1, r), push_up(p);
    }
    void modify(int lp, int &p, int l, int r, int i) {  //修改 f(x,i) 的式子 
        if(p==lp || !p) p=++on, tree[p]=tree[lp];
        if(l==r) tree[p].b=-tree[p].b, tree[p].c=-tree[p].c, tree[p].d=-tree[p].d;  //取相反数即可 
        else {
            if(i<=(l+r>>1)) modify(tree[lp].son[0], lc, l, l+r>>1, i);
            else modify(tree[lp].son[1], rc, (l+r>>1)+1, r, i);
            push_up(p);
        }
    }
    int query(int p, int l, int r, int x, int y, int z) {
        if(x<=l && r<=y) return ((ll) tree[p].b*z%mod*z+(ll) tree[p].c*z+tree[p].d)%mod;    //即求 bz^2+cz+d 
        return ((lc&&x<=(l+r>>1)?query(lc, l, l+r>>1, x, y, z):0)
               +(rc&&(l+r>>1)<y?query(rc, (l+r>>1)+1, r, x, y, z):0))%mod;
    }
#undef lc
#undef rc
}
using namespace Segment_Tree;

pair <int, int> tmp[mN];
void getrk() {  //去重，写得有点丑（
    rep(i, 1, n) tmp[i]=make_pair(a[i], i);
    sort(tmp+1, tmp+n+1);
    rep(i, 1, n) {
        if(tmp[i].first!=tmp[i-1].first) ++ork;
        rk[ork]=tmp[i].first, add(ork, tmp[i].second);
    }
}
int main() {
    n=read(), m=read();
    rep(i, 1, n) a[i]=read();
    getrk(), build(rt[0], 0, n);
    rep(i, 1, ork) lfor(t, i) modify(rt[i-1], rt[i], 0, n, ver[t]-1), modify(rt[i-1], rt[i], 0, n, ver[t]);
    //f(x, ver[t]) 和 f(x, ver[t]-1) 在 a[ver[t]] 变化时均需修改
    //因为修改时不想特判 ver[t]==1，所以下标从 0 到 n
    int ans=0, x, l, r;
    while(m--) {
        x=read()^ans, l=read()^ans, r=read()^ans;
        printf("%d\n", ans=(query(rt[upper_bound(rk, rk+ork+1, x)-rk-1], 0, n, l, r-1, x)+mod)%mod);
        //upper_bound-rk-1 找第一个小于等于 x 的数 
    }
    return 0;
}

本人代码常数巨大，欢迎各路神仙吊打。

这里放上 Push_Y 的写法，以供参考。

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int gin(){
    int s=0,f=1;
    char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

const int N=3e5+5,M=41,mod=1e9+7;
int n,m,idx,len;
int a[N],b[N],rt[N];
int lc[N*M],rc[N*M];
vector<int> pos[N];

struct node{
    int a,b,c;
    inline void qf(){a=-a,b=-b,c=-c;}
    inline int ans(int x){return (a*x%mod*x+b*x%mod+c+mod)%mod;}
}e[N*M];

inline int getid(int x){return lower_bound(b+1,b+len+1,x)-b;}

inline void pushup(int x){
    e[x].a=(e[lc[x]].a+e[rc[x]].a)%mod;
    e[x].b=(e[lc[x]].b+e[rc[x]].b)%mod;
    e[x].c=(e[lc[x]].c+e[rc[x]].c)%mod;
}

int build(int l,int r){
    int x=++idx;
    if(l==r){
        if(l!=0) e[x]=(node){1,(-a[l]-a[l+1])%mod,a[l]*a[l+1]%mod};
        return x;
    }
    int mid=l+r>>1;
    lc[x]=build(l,mid);
    rc[x]=build(mid+1,r);
    pushup(x);
    return x;
}

int upd(int x,int root,int l,int r,int v){
    if(x==root || !x) x=++idx,e[x]=e[root],lc[x]=lc[root],rc[x]=rc[root];
    if(l==r){
        e[x].qf();
        return x;
    }
    int mid=l+r>>1;
    if(v<=mid) lc[x]=upd(lc[x],lc[root],l,mid,v);
    else rc[x]=upd(rc[x],rc[root],mid+1,r,v);
    pushup(x);
    return x;
}

int query(int x,int l,int r,int L,int R,int X){
    if(L<=l && r<=R) return e[x].ans(X);
    int mid=l+r>>1,res=0;
    if(lc[x] && L<=mid) res+=query(lc[x],l,mid,L,R,X);
    if(rc[x] && mid<R ) res+=query(rc[x],mid+1,r,L,R,X);
    return res%mod;
}

signed main(){
    n=gin(),m=gin();
    for(int i=1;i<=n;i++)
        a[i]=b[i]=gin();
    sort(b+1,b+n+1);    
    len=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        pos[getid(a[i])].push_back(i);
    rt[1]=build(0,n);
    for(int i=2;i<=len+1;i++)
        for(int j=0;j<pos[i-1].size();j++){
            int v=pos[i-1][j];
            rt[i]=upd(rt[i],rt[i-1],0,n,v-1);
            rt[i]=upd(rt[i],rt[i-1],0,n,v);
        }
    int last=0;
    while(m--){
        int x=gin()^last,l=gin()^last,r=gin()^last;
        last=(query(rt[lower_bound(b+1,b+len+1,x)-b],0,n,l,r-1,x)+mod)%mod;
        printf("%lld\n",last);
    }
    return 0;
}