2019河北省大学生程序设计竞赛（重现赛）I.Twinkle

河北省大学生程序设计竞赛（重现赛）I.Twinkle"/>

2019河北省大学生程序设计竞赛（重现赛）I.Twinkle

题目链接：

题意：现在一个二维平面上有很多点，每个点有个亮度， q q q次询问，每次询问询问在 t t t时刻，一个矩形内的所有星星亮度的总和。星星的亮度从零时刻开始每一个时刻会增加 1 1 1，但是总亮度不会超过 c c c，如果超过 c c c亮度变成 0 0 0重新递增。

解题心得：这个CDQ分治写了好久，因为刚开始排序选错维度了，然后写了半天发现好像处理不出来。其实直接按照 x x x排序就行了，每次合并的时候按照 y y y的大小合并，再用一个树状数组维护一下时间维度就行了，但是树状数组要注意在维护的时候还要想办法处理是否超过 c c c，最后 c c c值太大还需要离散化一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 5e5+100;ll sum[maxn], cnt[maxn], ans[maxn], n, q, c, qcnt;
/** sum树状数组记录星星初始的亮度和* cnt记录树状数组内的星星的个数* ans记录最后的答案* qcnt记录cdq的坐标* */
vector <ll> ve;//用于离散化struct Node {ll x, y, aid, dir, va, pos;/** x,y是坐标记录* aid是记录答案的次序* dir如果是-2代表插入星星，-1代表答案-，1代表答案+* va表示星星的亮度或者时刻* pos代表离散化之后的值*/
}node[maxn];void init() {scanf("%lld%lld%lld", &n, &q, &c);for(ll i=1;i<=n;i++) {ll x, y, light;scanf("%lld%lld%lld", &x, &y, &light);ve.push_back(light);node[i] = {x, y, 0, -2, light, light};//初始化可以看成插入星星}qcnt = n+1;for(ll i=1;i<=q;i++) {ll x1, y1, x2, y2, t;scanf("%lld%lld%lld%lld%lld", &t, &x1, &y1, &x2, &y2);ve.push_back(c-t);//树状数组上的容斥node[qcnt++] = {x1-1, y1-1, i, 1, t, c-t};node[qcnt++] = {x2, y1-1, i, -1, t, c-t};node[qcnt++] = {x1-1, y2, i, -1, t, c-t};node[qcnt++] = {x2, y2, i, 1, t, c-t};}//离散化sort(ve.begin(), ve.end());ve.erase(unique(ve.begin(), ve.end()), ve.end());for(ll i=1;i<qcnt;i++) {ll pos = lower_bound(ve.begin(), ve.end(), node[i].pos) - ve.begin() + 1;node[i].pos = pos;}
}ll lowbit(ll x) {return x & -x;
}void add(ll x, ll va) {//需要维护初始化的和和星星的个数while(x <= ve.size()) {sum[x] += va;cnt[x] ++;x += lowbit(x);}
}pair <ll, ll> query(ll pos) {pair <ll, ll> Sum = {0, 0};while(pos > 0) {Sum.first += sum[pos];Sum.second += cnt[pos];pos -= lowbit(pos);}return Sum;
}void clr(ll x) {while(x <= ve.size()) {sum[x] = 0;cnt[x] = 0;x += lowbit(x);}
}Node temp[maxn];//临时用于归并排序
void cdq(ll l, ll r) {if(l == r) return ;ll mid = l + r >> 1;cdq(l, mid);cdq(mid+1, r);ll ls = l, rs = mid+1, cnt = 0;while(ls <= mid && rs <= r) {if(node[ls].y <= node[rs].y) {if(node[ls].dir == -2) add(node[ls].pos, node[ls].va);temp[cnt++] = node[ls++];} else {if(node[rs].dir == -1 || node[rs].dir == 1) {pair <ll, ll> Sum = query(node[rs].pos);pair <ll, ll> tot = query(ve.size());tot.first -=  Sum.first;tot.second -= Sum.second;ans[node[rs].aid] += (Sum.first + Sum.second * node[rs].va) * node[rs].dir;ans[node[rs].aid] += (tot.first + tot.second * node[rs].va - tot.second * (c + 1)) * node[rs].dir;//这里被题意坑了一波}temp[cnt++] = node[rs++];}}while(ls <= mid) temp[cnt++] = node[ls++];while(rs <= r) {if(node[rs].dir == -1 || node[rs].dir == 1) {pair <ll, ll> Sum = query(node[rs].pos);pair <ll, ll> tot = query(ve.size());tot.first -=  Sum.first;tot.second -= Sum.second;ans[node[rs].aid] += (Sum.first + Sum.second * node[rs].va) * node[rs].dir;ans[node[rs].aid] += (tot.first + tot.second*node[rs].va - tot.second * (c + 1)) * node[rs].dir;}temp[cnt++] = node[rs++];}for(ll i=l;i<=mid;i++)clr(node[i].pos);for(ll i=0;i<cnt;i++) node[l+i] = temp[i];
}bool cmp(Node a, Node b){if(a.x == b.x) return a.dir < b.dir;else return a.x < b.x;
}int main() {
//    freopen("1.in.txt", "r", stdin);init();sort(node+1, node+qcnt, cmp);cdq(1, qcnt-1);for(ll i=1;i<=q;i++) {printf("%lld\n", ans[i]);}return 0;
}