自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 22:07:24，当前版本为作者最后更新于2019-01-10 20:20:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

有一个长度为 $n$ 的区间，和 $q$ 次操作。每次操作给出 $l,r$ ，查询 $\sum_{}f(i,j)~~~l\le i<j\le r$ ，并将所有这样的 $f(i,j)$ 赋值为 $1$ 。数据 ** 强制在线 ** 。

如何解密

谁不知道亦或的逆运算是或异啊

Subtask#1 20pts

使用二维数组，用 $O(n^2)$ 的时间复杂度暴力处理每个查询，更新 $f$ 数组在范围 $[l,r]$ 之间的值。时间复杂度 $O(q\times n^2)$ 。

Subtask#2 30pts

观察到每个查询都是连续的区间，可以用 ** 树套树 ** 来维护这个问题。时间复杂度 $O(q\times \lg^2 n)$。空间复杂度 $O(n^2)$。

也可以使用 ** 分块套分块 ** 解决，时间复杂度 $O(q\times n)$ ，空间复杂度 $O(n^2)$ 。

观察到每个人认识的人在这个区间上都是 ** 连续 ** 的。对于一个人，我们只需记录这个人最左认识到的人的编号，和最右认识到的人的编号。注意到“认识”是有双向性的，所以我们可以只存储一个人向左最左认识到的人的编号，或另外一个。以最右认识到的人的编号为例，记为 $g(i)$。初始状态，所有人都不认识，一个人最右认识到的人是他自己，即 $g(i)=1$ 。在查询的时候，我们令区间 $[l,r]$ 的人互相认识，就是说对于这个区间上每一个人，如果这个人 $i$ 之前认识的最右的人在 $r$ 的左边，那么我们更新 $g(i)=\max\{g(i),r\}~~~l\le i\le r$。

时间复杂度 $O(q\times n)$ 。

Subtask#3 50pts

观察到上一段中所提到的 $g$ 数组是 ** 严格非降 ** 的。

考虑使用数据结构来维护这个 $g$ 数组。本题标程所使用的数据结构是 ** 线段树 ** 。

我们需要进行的更新是 $g(i)=\max\{g(i),r\}~~~l\le i\le r$ ，利用 $g$ 数组严格非降的性质，我们将一次操作分解为一下几个过程：

1. 求 $\sum_{i=l}^r g(i)$ 的值；

2. 二分求出区间 $[l,r]$ 上使 $g(i)<r$ 的最大的 $i$ ，记为 $k$ ；

3. 将区间 $[i,k]$ 赋值为 $r$。

$\space$

这样，我们就可以在 $O(q\times \lg_2 n)$ 的时间复杂度下解决这个问题。

代码展示

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000010;
typedef long long ll;
ll n,q,lstans,idx,l,r,sum[maxn*4],rv[maxn*4],lzy[maxn*4];
void pushdown(ll o,ll l,ll r)
{
    lzy[o<<1]=lzy[o<<1|1]=lzy[o];
    rv[o<<1]=rv[o<<1|1]=lzy[o];
    ll mid=(l+r)>>1;
    sum[o<<1]=(mid-l+1)*lzy[o];
    sum[o<<1|1]=(r-(mid+1)+1)*lzy[o];
    lzy[o]=0;
}
void Set(ll o,ll l,ll r,ll sl,ll sr,ll v)
{
    if(sl>r||sr<l)return;
    if(sl<=l&&r<=sr){lzy[o]=v;sum[o]=(r-l+1)*v;rv[o]=v;return;}
    ll mid=(l+r)>>1;
    if(lzy[o])pushdown(o,l,r);
    Set(o<<1,l,mid,sl,sr,v);
    Set(o<<1|1,mid+1,r,sl,sr,v);
    sum[o]=sum[o<<1]+sum[o<<1|1];
    rv[o]=rv[o<<1|1];
}
ll Query(ll o,ll l,ll r,ll ql,ll qr)
{
    if(ql>r||qr<l)return 0;
    if(ql<=l&&r<=qr)return sum[o];
    ll mid=(l+r)>>1;
    if(lzy[o])pushdown(o,l,r);
    return Query(o<<1,l,mid,ql,qr)+Query(o<<1|1,mid+1,r,ql,qr);
}
ll Find(ll o,ll l,ll r,ll v)
{
    if(l==r)return l;
    if(lzy[o])pushdown(o,l,r);
    ll mid=(l+r)>>1;
    if(rv[o<<1]>=v)return Find(o<<1,l,mid,v);
    return Find(o<<1|1,mid+1,r,v);
}
int main()
{
    scanf("%lld%lld",&n,&q);
    for(ll i=1;i<=n;i++)Set(1,1,n,i,i,i);
    while(q--)
    {
        scanf("%lld%lld",&l,&r);
        l^=lstans;r^=lstans;
        idx=Find(1,1,n,r);//the last number index witch <=r
        idx--;
        if(idx>=l)lstans=r*(idx-l+1)-Query(1,1,n,l,idx);
        else lstans=0;
        printf("%lld\n",lstans);
        if(idx>=l)Set(1,1,n,l,idx,r);
    }
    return 0;
}

闲言碎语

如果不强制离线有什么好的做法？

出题人本人也想不到 $qwq$ 。

为什么要弄Subtask呢？

因为本人的暴力（Subtask#2 的第三种解法）在随机数据下跑得比标程还快！

所以出题人设置了两组极限数据，专门卡时间复杂度为 $O(q\times n)$ 的暴力，一个卡从正面，一个卡从反面。怎么卡呢？当然是令 $r-l+1$ 偏大，对所有询问按从小到大（或者从大到小）排个序，就可以让这样的暴力跑出 $60s$ ，出题人是不是很聪明啊 $qwq$ ！

如果有人用暴力过了此题，请联系出题人哦！