luogu P5105 不强制在线的动态快速排序

时间：2021-01-02 23:40:04

前言

考试的时候居然想错了区间贡献，mdzz

思路

题目看着很方啊，难道要树套树？

但数据范围提醒我们，是nlogn的复杂度

Sort(S)的定义是不是很鬼畜

但我们不动脑子的打表容易发现

连续区间[1，n]内\(a_i^2-a_{i-1}^2\)为连续的奇数

（其实这里直接用初中的完全平方公式就好）

我们再次打表又发现了

连续的奇数的异或和，很有规律的嘛

可以直接O（1）求出

int xx(int x) {

    if(x%4==0) return 0;

	if(x%4==2) return 2;

	if(x%4==1) return x+x-1;

	return x+x+1;

}

根据异或的性质(a^a=0)

我们就能计算出任意连续一段的ans了，\(xx(l-1)\)^\(xx(r)\)

虽说允许重复的集合S

但区间如果重叠，他也只计算一次答案，手玩一下很容易看出

也就是集合S还是不允许重复的(重复的删掉是不影响答案的)

合并直接算就好了

我们现在需要一个只需要支持区间更改贡献的数据结构

lsh+线段树真香

struct node {

	int l,r,lazy;

    int mi,ma,sum;

	int full,k;

} e[maxn<<4];

/*

	mi,ma维护区间[l,r]最小值

	lazy懒惰标记

	ok判断区间[l,r]是否全部被计算答案

	k判断[mid,mid+1]之间是否连接

	ans就是ans啦

*/

ps：可能我的线段树调试的时候打了太多补丁，肯定有比我写的好得多的代码

但也是不难理解的，重要部分我们加以注释

关于int，是会炸的，反正我的数据灰渣

另外提醒

千万别开小了数组,一组询问是两个数偶，我一直报WA

错误

主席树写多了，左右孩子和l,r老是搞混了，mdzz

代码

#include <bits/stdc++.h>

#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int maxn=3e5+7;

const ll inf=0x3f3f3f3f3f3f3f3fLL;

int read() {

    int x=0,f=1;char s=getchar();

    for(; s>'9'||s<'0'; s=getchar()) if(s=='-') f=-1;

    for(; s>='0'&&s<='9'; s=getchar()) x=x*10+s-'0';

    return x*f;

}

ll xx(ll x) {

    if(x%4==0) return 0;

    if(x%4==2) return 2;

    if(x%4==1) return x+x-1;

    return x+x+1;

}

ll calc(ll l,ll r) {return xx(r)^xx(l-1);}

struct node {

    int l,r;

    ll mi,ma,sum;

	bool full,k,lazy;

} e[maxn<<4];

int lsh[maxn<<1],len;

void pushup(int rt) {

    if(e[rt].full) return;

    if(e[rt].k) // 区间[mid,mid+1]贡献 需要计算

        e[rt].sum=e[rt<<1].sum^e[rt<<1|1].sum^calc(lsh[e[rt<<1].r]+1,lsh[e[rt<<1|1].l]);

    else if(e[rt<<1].ma==-inf||e[rt<<1|1].mi==inf) //只有一边有值

        e[rt].sum=e[rt<<1].sum^e[rt<<1|1].sum;

    else //暴力计算

        e[rt].sum=e[rt<<1].sum^e[rt<<1|1].sum^(e[rt<<1|1].mi*e[rt<<1|1].mi-e[rt<<1].ma*e[rt<<1].ma);

    e[rt].ma=max(e[rt<<1].ma,e[rt<<1|1].ma);

    e[rt].mi=min(e[rt<<1].mi,e[rt<<1|1].mi);

}

void tag(int rt) {//区间全部计算ans

    e[rt].sum=calc(lsh[e[rt].l]+1,lsh[e[rt].r]);

    e[rt].full=1;

    e[rt].mi=lsh[e[rt].l];

    e[rt].ma=lsh[e[rt].r];

}

void pushdown(int rt) {

    if(e[rt].lazy==0) return;

    if(e[rt].lazy) {//显然

        tag(rt<<1);tag(rt<<1|1);

        e[rt<<1].lazy=e[rt<<1|1].lazy=1;

        e[rt].lazy=0;

    }

}

void build(int l,int r,int rt) {//显然

    e[rt].l=l,e[rt].r=r;

    e[rt].ma=-inf,e[rt].mi=inf;

    if(l==r) return;

    int mid=(l+r)>>1;

    build(l,mid,rt<<1);

    build(mid+1,r,rt<<1|1);

}

void modify(int L,int R,int rt) {

    if(L<=e[rt].l&&e[rt].r<=R) {

        tag(rt);

        e[rt].lazy=1;

        return;

    }

    if(e[rt].full) return;//如果计算过就不用在计算了

    pushdown(rt);

    int mid=(e[rt].l+e[rt].r)>>1;

    if(L<=mid) modify(L,R,rt<<1);

    if(R>mid) modify(L,R,rt<<1|1);

    if(L<=mid&&R>mid) e[rt].k=1;//区间两边都经过，中间也一定经过，k=1

    pushup(rt);

}

struct edge {int opt,x,y;} Q[maxn];//询问

main() {

	//read and lsh

    int n=read();

    FOR(i,1,n) {

        Q[i].opt=read();

        if(Q[i].opt==1) lsh[++len]=Q[i].x=read(),lsh[++len]=Q[i].y=read();

    }

    sort(lsh+1,lsh+1+len);

    len=unique(lsh+1,lsh+1+len)-lsh-1;

    build(1,len,1);

    FOR(i,1,n) {

        if(Q[i].opt==2) continue;

        Q[i].x=lower_bound(lsh+1,lsh+1+len,Q[i].x)-lsh;

        Q[i].y=lower_bound(lsh+1,lsh+1+len,Q[i].y)-lsh;

    }

    //work

    FOR(i,1,n) {

        if(Q[i].opt==2)

            cout<<e[1].sum<<"\n";

        else

            modify(Q[i].x,Q[i].y,1);

    }

    return 0;

}

相关文章