题解 P5125 【不认识】

hsfzLZH1 · 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 数组严格非降的性质，我们将一次操作分解为一下几个过程：

求 \sum_{i=l}^r g(i) 的值；
二分求出区间 [l,r] 上使 g(i)<r 的最大的 i ，记为 k ；
将区间 [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 ！

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