相关链接
题目传送门:http://codeforces.com/contest/781/problem/E
代码参考:http://codeforces.com/contest/781/submission/25269119
解题报告
这题我们先考虑没有墙会害怕的版本
这样的话,我们想象一下是墙冲向一排点
于是搞一个线段树支持区间赋值,区间查询就可以了!
现在考虑加上害怕的限制
那我们可以用二维线段树!
但好难写QwQ ←这货写到一半就弃坑了
于是就去看别人的代码
然后看到了毛爷爷的代码 (毛爷爷这场暴跌 默哀 _(:з」∠)_
)
然后发现这题又可以暴力………
我们考虑将每一次分开的点打成一包
算上最开始的,不难发现总共只有$O(w+2n)$个包
那每一个包我们插到线段树中,此时总包数是$O((w+2n) \log (w+2n))$的
那么每一次查询我们就暴力每一个节点,于是均摊的复杂度仍然是$O(\log n)$的
代码好写还跑得飞快!
这种有一点暴力思想的数据结构题,我还真的是一点想不出来啊!
比如BZOJ 4712,真的是一点都没往那边想啊!
我一定要在科技树上点亮这个技能!
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5000000; const int M = 200009; const int MOD = 1000000007; int hit,wid,n,cnt; struct Pack{int h,sum,del;}p[N]; struct Wall{int h,l,r,s;}wall[M]; class Segment_Tree{ int ans_tmp,tot,root,ch[M][2]; stack<int> s[M]; public: inline void insert(int p, int id) { insert(root, 1, wid, p, id); } inline int query(int h, int l, int r) { ans_tmp = 0; query(root, 1, wid, l, r, h); return ans_tmp; } private: void insert(int &w, int l, int r, int p, int v) { if (!w) w = ++tot; s[w].push(v); if (l < r) { int mid = l + r + 1 >> 1; if (p < mid) insert(ch[w][0], l, mid-1, p, v); else insert(ch[w][1], mid, r, p, v); } } void query(int w, int l, int r, int L, int R, int h) { if (L <= l && r <= R) { while (!s[w].empty() && p[s[w].top()].h <= h) { if (!p[s[w].top()].del) { p[s[w].top()].del = 1; (ans_tmp += p[s[w].top()].sum) %= MOD; } s[w].pop(); } } else { int mid = l + r + 1 >> 1; if (L < mid) query(ch[w][0], l, mid-1, L, R, h); if (mid <= R) query(ch[w][1], mid, r, L, R, h); } } }SGT; inline int read() { char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main() { hit = read(); wid = read(); n = read(); for (int i=1;i<=n;i++) { wall[i].h = read(); wall[i].l = read(); wall[i].r = read(); wall[i].s = read(); } for (int i=1;i<=wid;i++) { p[++cnt].h = hit + 1; p[cnt].sum = 1; SGT.insert(i, cnt); } sort(wall+1, wall+1+n, [](const Wall &A, const Wall &B){return A.h > B.h;}); for (int i=1,h_mx,tmp;i<=n;i++) { tmp = SGT.query(wall[i].h + wall[i].s, wall[i].l, wall[i].r); p[++cnt].sum = tmp; p[cnt].h = wall[i].h; p[++cnt].sum = tmp; p[cnt].h = wall[i].h; if (wall[i].l == 1) SGT.insert(wall[i].r+1, cnt-1); else SGT.insert(wall[i].l-1, cnt-1); if (wall[i].r == wid) SGT.insert(wall[i].l-1, cnt); else SGT.insert(wall[i].r+1, cnt); } int vout = 0; for (int i=1;i<=cnt;i++) (vout += (p[i].del ^ 1) * p[i].sum) %= MOD; printf("%d\n",vout); return 0; }