注册网站用于跳转虚拟货币网站违法,网站空间转移,wordpress 编辑器增加翻译按钮,wordpress该字体传送门 之前听别人说CDQ分治不难学#xff0c;今天才知道果真如此。之前一直为自己想不到CDQ的方法二很不爽#xff0c;今天终于是想出来了一道了#xff0c;太弱…… cdq分治主要就是把整段区间分成两半#xff0c;然后用左区间的值去更新右区间的答案#xff0c;每次把… 传送门 之前听别人说CDQ分治不难学今天才知道果真如此。之前一直为自己想不到CDQ的方法二很不爽今天终于是想出来了一道了太弱…… cdq分治主要就是把整段区间分成两半然后用左区间的值去更新右区间的答案每次把区间折半。对于本题来说时间复杂度T(N)T(N/2)O(NlogN) T(N)O(Nlog2N) /**************************************************************Problem: 2683Language: CResult: AcceptedTime:6204 msMemory:35184 kb
****************************************************************/#include cstdio
#include algorithm
using namespace std;
#define MAXN 200005
struct Node {int t, x, y, v, k;inline bool operator (const Noder) const {if(x r.x y r.y) return t r.t;else if(x r.x) return y r.y;else return x r.x;}
} q[MAXN 2], nq[MAXN 2];
int n, cnt, ans;
inline void GET(int n) {n 0; char c;do c getchar(); while(0 c || c 9);do n n * 10 c - 0, c getchar(); while(0 c c 9);
}
namespace BIT {int t[MAXN 2];inline void Add(int x, int v) {for(; x n; x x-x) t[x] v;}inline int Query(int x, int s 0) {for(; x; x - x-x) st[x];return s;}
}
void cdq(int l, int r) {if(l r) return;using namespace BIT;int mid (l r) 1, lp l, rp mid1;for(int i l; i r; i)if(q[i].t mid q[i].k 1) Add(q[i].y, q[i].v);else if(q[i].t mid q[i].k 2) q[i].v Query(q[i].y);for(int i l; i r; i) {if(q[i].t mid q[i].k 1) Add(q[i].y, -q[i].v);if(q[i].t mid) nq[lp ] q[i];else nq[rp ] q[i];}for(int i l; i r; i) q[i] nq[i];cdq(l, mid); cdq(mid1, r);
}
int main() {scanf(%d, n);int op, x, y, a, b;while(~scanf(%d, op) 3 ! op) {if(1 op) {GET(x); GET(y); GET(a);q[ cnt] { cnt, x, y, a, 1 };}else {GET(x); GET(y); GET(a); GET(b);q[ cnt] { cnt, x-1, y-1, 0, 2 };q[ cnt] { cnt, x-1, b, 0, 2 };q[ cnt] { cnt, a, y-1, 0, 2 };q[ cnt] { cnt, a, b, 0, 2 };}}sort(q1, qcnt1);cdq(1, cnt);for(int i 1; i cnt; i)if(q[i].k 2) {ans q[i].v - q[i1].v - q[i2].v q[i3].v;printf(%d\n, ans); i 3;}return 0;
} 转载于:https://www.cnblogs.com/geng4512/p/5296858.html
