自动搬运

查看原文

来自洛谷，原作者为

	LPA20020220 **

搬运于2025-08-24 21:55:22，当前版本为作者最后更新于2018-09-12 21:24:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

显然一份区域的贡献为覆盖其上的扇形半径的第k大的平方。所以我们可以按扇形的半径从大到小排序， 每次等于一个区间赋值的操作， 如果一个段被覆盖k次就产生贡献。（貌似比扫描线常数更小， 而且还好写...貌似突然rk1了？？）

维护一个区间最大最小值判断是否应该递归计算。 另外， 将贡献过的区间的size赋值为0， 避免重复计算。

代码如下：

    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cctype>
    #include <algorithm>
    #include <cstdlib>
    #define R register
    #define IN inline
    #define W while
    #define gc getchar()
    #define MX 2000500
    #define ll long long
    bool neg;
    template <class T>
    IN void in(T &x)
    {
    	x = 0; R char c = gc;
    	for (; !isdigit(c); c = gc)
    	if(c == '-') neg = true;
    	for (;  isdigit(c); c = gc)
    	x = (x << 1) + (x << 3) + c - 48;
    	if(neg) neg = false, x = -x;
    }
    int q, seg, kth, tar; struct Node {int siz, mn, mx, tag;} tree[MX << 2];
    struct opt {int h, lef, rig;} req[100005];
    IN bool operator < (const opt &x, const opt &y) {return x.h > y.h;}
    namespace SGT
    {
    	#define ls (now << 1)
    	#define rs (now << 1 | 1)
    	IN void pushup(R int now)
    	{
    		tree[now].mn = std::min(tree[ls].mn, tree[rs].mn);
    		tree[now].mx = std::max(tree[ls].mx, tree[rs].mx);
    		tree[now].siz = tree[ls].siz + tree[rs].siz;
    	}
    	IN void pushdown(R int now)
    	{
    		if(tree[now].tag)
    		{
    			if(ls) tree[ls].mn += tree[now].tag, tree[ls].mx += tree[now].tag, tree[ls].tag += tree[now].tag;
    			if(rs) tree[rs].mn += tree[now].tag, tree[rs].mx += tree[now].tag, tree[rs].tag += tree[now].tag;
    			tree[now].tag = 0;
    		}
    	}
    	void build(R int now, R int lef, R int rig)
    	{
    		if(lef == rig) return tree[now].siz = 1, void();
    		int mid = lef + rig >> 1;
    		build(ls, lef, mid), build(rs, mid + 1, rig);
    		pushup(now);
    	}
    	int query(R int now, R int lef, R int rig, R int lb, R int rb)
    	{
    		if(lef > rig) return 0;
    		if(tree[now].mn >= kth) return 0;
    		if(lef >= lb && rig <= rb)
    		{
    			if(tree[now].mx < tar) {tree[now].tag += 1, tree[now].mx++, tree[now].mn++; return 0;}
    			if(tree[now].mn == tar) {int ret = tree[now].siz; tree[now].siz = 0; tree[now].mx = tree[now].mn = kth; return ret;}
    			int ret = 0, mid = lef + rig >> 1;
    			pushdown(now);
    			if(ls) ret += query(ls, lef, mid, lb, rb); if(rs) ret += query(rs, mid + 1, rig, lb, rb);
    			pushup(now); return ret;
    		}
    		int mid = lef + rig >> 1, ret = 0; pushdown(now);
    		if(lb <= mid) ret += query(ls, lef, mid, lb, rb);
    		if(rb > mid) ret += query(rs, mid + 1, rig, lb, rb);
    		pushup(now); return ret;
    	}
    	#undef ls
    	#undef rs
    }
    ll ans, sum;
    int main(void)
    {
    
    	in(q), in(seg), in(kth); tar = kth - 1;
    	SGT::build(1, 1, seg << 1);
    	for (R int i = 1; i <= q; ++i) in(req[i].h), in(req[i].lef), in(req[i].rig), req[i].lef += 1 + seg, req[i].rig += seg;
    	std::sort(req + 1, req + 1 + q);
    	for (R int i = 1; i <= q; ++i)
    	{
    		sum = 0;
    		if(req[i].rig < req[i].lef)
    		{
    			sum += SGT::query(1, 1, seg << 1, req[i].lef, seg << 1);
    			sum += SGT::query(1, 1, seg << 1, 1, req[i].rig);
    			ans += 1ll * req[i].h * req[i].h * sum;
    		}
    		else
    		{
    			sum += SGT::query(1, 1, seg << 1, req[i].lef, req[i].rig);
    			ans += 1ll * req[i].h * req[i].h * sum;
    		}
    	}
    	printf("%lld", ans);
    }