bzoj

luogu

## 题解

$$f[i][j]=f[i][j + 1] + f[i+1][j] – f[i + 1][j + 1]$$

$$f[i][j]=f[i][j+1]$$

$$f[i][j]=f[i + 1][j]$$

$$f[i][j]=f[i][j + 1] + f[i+1][j] – f[i + 1][j + 1]$$

$$f[i][j]-f[i+1][j]=f[i][j+1]-f[i+1][j+1]$$

$$f[i][j]-f[i+1][j]=0$$

$$f[i][j]-0=f[i][j+1]-0$$

$$f[i][j]-f[i+1][j]=f[i][j+1]-0$$

$$f[i][j]=f[i+1][j]+f[i][j+1]-f[x2+1][y2+1]$$

#include<bits/stdc++.h>
#define N 1000005
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define Re register
#define ll long long
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mp std::make_pair
#define Judge_Online
struct tree{
int sum;
bool fl;
}t[N << 2];
struct flower_cow{
int x, y, id;
friend bool operator < (flower_cow a, flower_cow b) {return a.y < b.y;}
}f[N], c[N];
struct block{
int l, r, y, id, opt;
friend bool operator < (block a, block b) {return a.y < b.y || a.y == b.y && a.opt < b.opt;}
}b[N << 1];
int tot, rd[N], T, n, m, xmax, ymax, ans[N];
inline void pushdown (int u)
{
if (t[u].fl)
{
t[ls].sum = t[rs].sum = 0;
t[ls].fl = t[rs].fl = 1;
t[u].fl = 0;
}
}
int a[N];
inline int query (int u, int l, int r, int L, int R)
{
#ifndef Judge_Online
if (u == 1)
{
printf("Now : \n");
fo (i, 0, xmax) printf("%d ", a[i]);
puts("");
}
#endif
if (l <= L && R <= r) return t[u].sum;
pushdown(u);
int mid = L + R >> 1, ret = 0;
if (l <= mid) ret += query(ls, l, r, L, mid);
if (mid < r) ret += query(rs, l, r, mid + 1, R);
return ret;
}
inline void clean (int l, int r)
{
fo (i, l, r) a[i] = 0;
printf("clean[%d, %d] : \n", l, r);
fo (i, 0, xmax) printf("%d ", a[i]); puts("");
}
inline void addpoint (int p, int val, int opt)
{
opt ? a[p] = val : a[p] += val;
fo (i, 0, xmax) printf("%d ", a[i]); puts("");
}
inline void modify0 (int u, int l, int r, int L, int R)
{
#ifndef Judge_Online
if (u == 1) clean(l, r);
#endif
if (l <= L && R <= r) {t[u].fl = 1; t[u].sum = 0; return;}
pushdown(u);
int mid = L + R >> 1;
if (l <= mid) modify0(ls, l, r, L, mid);
if (mid < r) modify0(rs, l, r, mid + 1, R);
t[u].sum = t[ls].sum + t[rs].sum;
}
inline void add (int u, int pos, int val, int L, int R, int opt)
{
#ifndef Judge_Online
if (u == 1) addpoint(pos, val, opt);
#endif
if (L == R) {opt ? t[u].sum = val : t[u].sum += val; return;}
pushdown(u);
int mid = L + R >> 1;
if (pos <= mid) add(ls, pos, val, L, mid, opt);
else add(rs, pos, val, mid + 1, R, opt);
t[u].sum = t[ls].sum + t[rs].sum;
}
std::set<int> s;
std::map<std::pair<int, int>, int> p;
int main ()
{
scanf("%d", &T);
fo (i, 1, T)
{
int x1, y1, x2, y2;
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
b[++tot] = (block) {x1, x2, y1 - 1, i, -1};
b[++tot] = (block) {x1, x2, y2, i, 1};
p[mp(x1 - 1, y1 - 1)] = i;
ymax = std::max(ymax, y2); xmax = std::max(xmax, x2);
}
scanf("%d", &m); fo (i, 1, m) {scanf("%d %d", &f[i].x, &f[i].y); ymax = std::max(ymax, f[i].y); xmax = std::max(xmax, f[i].x);}
scanf("%d", &n); fo (i, 1, n) {scanf("%d %d", &c[i].x, &c[i].y); ymax = std::max(ymax, c[i].y); xmax = std::max(xmax, c[i].x); c[i].id = i;}
std::sort(b + 1, b + tot + 1); std::sort(f + 1, f + m + 1); std::sort(c + 1, c + n + 1);
s.insert(0); s.insert(xmax + 2); int on = n;
T = tot;
fd (y, ymax, 1)
{
while (y == b[T].y)
{
if (b[T].opt == 1)
{
int r = *s.upper_bound(b[T].r + 1) - 1;
rd[b[T].id] = query(1, b[T].r + 1, r, 1, xmax);
r = *s.upper_bound(b[T].l - 1) - 1;
int nans = query(1, b[T].l - 1, r, 1, xmax);
add(1, b[T].l - 1, nans, 1, xmax, 1);
s.insert(b[T].l); s.insert(b[T].r + 1);
}
else
{
s.erase(b[T].l); s.erase(b[T].r + 1);
add(1, b[T].l - 1, -rd[b[T].id], 1, xmax, 0);
}
modify0(1, b[T].l, b[T].r, 1, xmax);
--T;
}
while (y == f[m].y)
{
int l = *(--s.upper_bound(f[m].x));
add(1, f[m].x, 1, 1, xmax, 0);
//            add(1, l, -1, 1, xmax, 0);
--m;
}
while (y == c[n].y)
{
int r = *s.upper_bound(c[n].x) - 1, now;
ans[c[n].id] = query(1, c[n].x, r, 1, xmax);
--n;
}
}
fo (i, 1, on) {printf("%d\n", ans[i]);}
return 0;
}


#ifndef Online_Judge

#endif


(如果 xzy 大佬还在的话肯定会喷死我的毒瘤压行 233333)