1 条题解

  • 0
    @ 2021-8-27 17:37:14

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

    欢迎踩博客

    前置知识:

    可持久化线段树。

    题意:

    • 给出一个长度为 nn 的数列 aia_i

    • mm 次在线询问,每次询问求出 i=lr1xai×xai+1\sum\limits_{i=l}^{r-1}|x-a_i|\times|x-a_{i+1}|

    • n,m3×105n,m\le3\times10^5

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

    分析:

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

    不过离散化后,我们可能只需要开 3×1053\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} $$

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

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

    注意到当 xx 增大的过程中,xxaia_i 的关系最多改变一次(从 xaix\le a_ix>aix>a_i),并且总是当 xx 超过 aia_i 的时候,fx,if_{x,i}fx,i1f_{x,i-1} 会改变。因此对于每个 aia_i 建一棵线段树,并使用主席树维护这 nn 棵树。每次 xx 超过 aia_i 时,在上一棵树的基础上修改 fx,i1f_{x,i-1}fx,if_{x,i},就可以解决问题了。

    思路:

    1. 对每一个 aia_i 开一棵线段树,并使用主席树维护。

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


    ##code:

    #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;
    }
    

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

    特别申明:本题解为团队成员 ATue 所写。

    • 1

    信息

    ID
    185
    时间
    1000~2000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    9
    已通过
    6
    上传者