[toc]

题目

传送门

这里的加入是把每个元素看成一个集合！！！

解法

$\sf{FBI\ Warning}$：最好先跳到 “我 没 学 懂” 板块开始看，不然你可能会被我绕进去。

这道题主要是讲一下 整体二分。

整体二分顾名思义，就是有一坨数，规定一个 $\text{mid}$ 进行二分 （好像一点也不清楚）。

思考一下普通的二分，我们其实是帮助 一个数值 $ans$ 选择一个合适的值。整体二分就是帮助很多个数值选择一个合适的值。

接下来说一下算法流程吧。

对值域进行二分。我们定义两个序列 $L$ 与 $R$，分别向下递归至 $[l,\text{mid}],[\text{mid}+1,r]$。对于此题我们的 $\text{mid}$ 就是 假定 第 $C$ 大的数，那么对于这次遍历大于 $\text{mid}$ 的数就是能对结果产生影响的，设目前为止大于 $\text{mid}$ 的数的个数为 $num$。

首先我们的时间戳是有序的，这个就不用排序了。对于每个询问与插入，我们可以进行分类讨论。

• 操作为询问，$num$ 小于询问要求的 $C$。这说明我们把 $mid$ 的值调大了，我们将 $C$ 减去 $num$，再在 $[l,mid]$ 中选择新值（即插入 $L$）。（注意这里的 $mid$ 是可以取到的，因为判断条件是 $num < C$）
• 操作为询问，$num$ 大于等于要求的 $C$。我们先前判断用的是严格大于才加入树状数组，所以等于的情况不会触及 $mid$。从 $[mid+1,r]$ 中找就行了。
• 操作为插入，$C>mid$。这种权值插入 $R$，再在树状数组中更新就行了。
• 操作为插入，$C\le mid$。这种权值显然不能贡献 $[mid+1,r]$ 的 $mid’$，插入 $L$ 就行了。

$\text{Update on 2021.2.16}$：

我之前写了个啥，我怎么这么幼稚。

这题需要维护区间加和区间和。树状数组是单点加，为了保证时间复杂度容易想到差分的思想。

然后可以看看 我的另一篇博客，讲了树状数组怎么维护。

看到树状数组也许你看不懂 （当然你可以写线段树，比树状数组好理解得多，我是因为我是 $250$ 才会去做的 $QwQ$），接下来我会详细讲解树状数组，如果没有看懂可以私信或评论哟！ （蒟蒻求赞）

先来一张图（这个可以结合代码观看，这个部分感觉网上有些代码可能有问题就比如我看的那份树状数组代码）：

我们在 $2$ 这个节点加了 $1$ 这个数值，用另一个数组加了 $2-1=1$ 这个数值。

接下来假设我们 $ask(x=5)$。因为这相当于是一个前缀和：对于 $c1[]$，记录的就是在 $[1,x]$ 之间有多少个添加的 $1$（注意这里也可以改成 $-1$，这个部分我就不讲了，一通百通）。而对于 $c2[]$，记录的就是每个位置上被添加的次数 $*$ （位置 $ - 1$）（注意这里的两个数组已经完成 $ask$ 中的累加）。

那么 $\sum c1*x-\sum c2$ 对应在图上就是一条长的橙色的线段减去短的橙色的线段，正好就是黄色的线段：这个 $1$ 到 $x$ 之间的位置个数。

总结一下：这个 $ask$ 函数返回的值就是 $x$ 与之前每个位置的距离 $*$ 这个位置被添加 $1$ 的个数。

好的我们再放一张图，来解释最终的答案。

$ask(L-1)=5-2+1=4$，$ask®=(8-2+1)+(8-7+1)=9$。

相减即为所求：在 $[L,R]$ 区间内大于 $mid$ 的数的个数。

我竟然写完了 $QwQ$（希望不要被布布扣转载小声哔哔）。

代码

#include <cstdio>
#define int long long

const int N = 5e4 + 5;
int n, m, p[N], ans[N], op[N], l[N], r[N], c1[N], c2[N], c[N], lef[N], rig[N];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) < '0' || s > '9') if(s == '-') f = -1;
    while(s >= '0' && s <= '9') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

int lowbit(const int x) {return x & -x;}

void add(const int x, const int k) {
    for(int i = x; i <= n; i += lowbit(i))
        c1[i] += k, c2[i] += k * (x - 1);
}

int ask(const int x) {
    int r = 0;
    for(int i = x; i; i -= lowbit(i))
        r += c1[i] * x - c2[i];
    return r;
}

void cdq(const int L, const int R, const int down, const int up) {
    if(L > R || down > up) return;
    if(down == up) {for(int i = L; i <= R; ++ i) ans[p[i]] = up; return;}
    int mid = up + down >> 1; int lenl = 0, lenr = 0;
    for(int i = L; i <= R; ++ i) {
        int pos = p[i];
        if(op[pos] & 2) {
            int num = ask(r[pos]) - ask(l[pos] - 1);
            if(num < c[pos]) lef[++ lenl] = pos, c[pos] -= num;
            else rig[++ lenr] = pos;
        }
        else {
            if(c[pos] > mid) add(l[pos], 1), add(r[pos] + 1, -1), rig[++ lenr] = pos;
            else lef[++ lenl] = pos;
        }
    }
    for(int i = 1; i <= lenl; ++ i) p[L + i - 1] = lef[i];
    for(int i = 1; i <= lenr; ++ i) {
        p[L + i + lenl - 1] = rig[i];
        if(op[p[L + i + lenl - 1]] & 1) add(l[p[L + i + lenl - 1]], -1), add(r[p[L + i + lenl - 1]] + 1, 1);
    }
    cdq(L, L + lenl - 1, down, mid); cdq(L + lenl, R, mid + 1, up);
}

signed main() {
    n = read(), m = read();
    for(int i = 1; i <= m; ++ i)
        p[i] = i, op[i] = read(), l[i] = read(), r[i] = read(), c[i] = read();
    cdq(1, m, -n, n);
    for(int i = 1; i <= m; ++ i)
        if(op[i] & 2) printf("%lld\n", ans[i]);
    return 0;
}

我 没 学 懂

是这样的，在考场上又写挂了。

有一个更易理解的方法：二分 $\text{mid}$，将比它大的数加入线段树。查询时询问区间内大于 $\text{mid}$ 的数的个数，如果 $c\le \text{Query}$，那么这个值就应该在 $[\text{mid}+1,r]$ 之间。

关于复杂度，每一层都有 $m+q$ 个操作，一共有 $\log n$ 层，一次操作是 $\mathcal O(\log n)$ 的，所以总复杂度是 $\mathcal O((m+q)\cdot \log^2 n)$ 哒！

#include <cstdio>
#define rep(i,_l,_r) for(signed i=(_l),_end=(_r);i<=_end;++i)

typedef long long ll;
const int maxn=5e4+5;

int n,m,tag[maxn<<2];
bool is[maxn];
ll t[maxn<<2],ans[maxn];
struct node {int l,r,op,id; ll c;} s[maxn],tl[maxn],tr[maxn];

void pushDown(int o,int l,int r) {
	if(!tag[o]) return;
	int mid=l+r>>1;
	tag[o<<1]+=tag[o],tag[o<<1|1]+=tag[o];
	t[o<<1]+=1ll*(mid-l+1)*tag[o],t[o<<1|1]+=1ll*(r-mid)*tag[o];
	tag[o]=0;
}

void pushUp(int o) {t[o]=t[o<<1]+t[o<<1|1];}

ll Query(int o,int l,int r,int L,int R) {
	if(l>R || r<L) return 0;
	if(l>=L && r<=R) return t[o];
	int mid=l+r>>1;
	pushDown(o,l,r);
	return Query(o<<1,l,mid,L,R)+Query(o<<1|1,mid+1,r,L,R);
}

void modify(int o,int l,int r,int L,int R,int k) {
	if(l>R || r<L) return;
	if(l>=L && r<=R) return (void)(tag[o]+=k,t[o]+=1ll*(r-l+1)*k);
	int mid=l+r>>1;
	pushDown(o,l,r);
	modify(o<<1,l,mid,L,R,k),modify(o<<1|1,mid+1,r,L,R,k);
	pushUp(o);
}

void dicon(int l,int r,int ql,int qr) {
	if(ql>qr || l>r) return;
	if(l==r) {
		rep(i,ql,qr) ans[s[i].id]=l;
		return;
	}
	int mid=l+r>>1,totl=0,totr=0; ll tmp;
	rep(i,ql,qr)
		if(s[i].op==1) {
			if(s[i].c>mid) modify(1,1,n,s[i].l,s[i].r,1),tr[++totr]=s[i];
			else tl[++totl]=s[i];
		}
		else {
			tmp=Query(1,1,n,s[i].l,s[i].r);
			if(s[i].c<=tmp) tr[++totr]=s[i];
			else s[i].c-=tmp,tl[++totl]=s[i];
		}
	rep(i,1,totl) s[ql+i-1]=tl[i];
	rep(i,1,totr) {
		s[ql+totl+i-1]=tr[i];
		if(tr[i].op==1) modify(1,1,n,tr[i].l,tr[i].r,-1);
	}
	dicon(l,mid,ql,ql+totl-1),dicon(mid+1,r,ql+totl,ql+totl+totr-1);
}

signed main() {
	scanf("%d %d",&n,&m);
	rep(i,1,m) scanf("%d %d %d %lld",&s[i].op,&s[i].l,&s[i].r,&s[i].c),s[i].id=i,is[i]=(s[i].op==2);
	dicon(-n,n,1,m);
	rep(i,1,m) if(is[i]) printf("%lld\n",ans[i]);
	return 0;
}