[Luogu P3997] [BZOJ 4418] [SHOI2013]扇形面积并
程序员文章站
2022-03-21 07:53:18
...
洛谷传送门
BZOJ传送门
题目描述
给定 个同心的扇形,求有多少面积,被至少 个扇形所覆盖。
输入输出格式
输入格式:
第一行是三个整数 ,,。 代表同心扇形个数,代表将的角度
区间平均分成 份。
从第二行开始的 行,每行三个整数 ,,。描述了一个圆心在原点的扇形,半径为,圆心角是从弧度
到( 不一定小于 )。
输出格式:
输出一个整数 ,等于至少 个扇形所覆盖的总面积。
数据保证答案在范围内。
输入输出样例
输入样例#1:
3 8 2
1 -8 8
3 -7 3
5 -5 5
输出样例#1:
76
输入样例#2:
2 4 1
4 -4 2
1 -4 4
输出样例#2:
98
说明
解题分析
显然一份区域的贡献为覆盖其上的扇形半径的第大的平方。所以我们可以按扇形的半径从大到小排序, 每次等于一个区间赋值的操作, 如果一个段被覆盖次就产生贡献。(貌似比扫描线常数更小, 而且还好写…)
维护一个区间最大最小值判断是否应该递归计算。 另外, 将贡献过的区间的赋值为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);
}