题面
https://darkbzoj.tk/problem/2658
题解
前置知识
-
笛卡尔树 https://blog.csdn.net/qq_36056315/article/details/79845193
-
FHQ Treap https://blog.csdn.net/CABI_ZGX/article/details/79963427
-
或普通Treap http://www.360doc.com/content/19/0120/11/5315_810146183.shtml
看见“至少包含一个”这种字眼，多少感觉正向做会比取补要来得麻烦一些，于是取补，从矩形总数(frac{R(R+1)}{2} imesfrac{C(C+1)}{2})中减去那些不包含任何点的。
在统计不包含任何点的矩形的个数时，先从上到下枚举矩形的下边所在直线。（不妨设x轴正方向向右，y轴正方向向下）设当前直线为(y=cury)，对横坐标x=1~R，定义h[x]为所有横坐标为x，纵坐标(leq cury)的点中，纵坐标最大者的纵坐标。那么所有下边在(y=cury)上的矩形的总数就是
而第二项可以转化
对h数组建出笛卡尔树后，分别对树上每一个节点u考虑贡献：h[u]对点对(i,j)有贡献，当且仅当(i{leq}u{leq}j)且i,j都在u的子树内。所以u此时的总贡献是(h[u]*(sz[c[u][0]]+1)(sz[c[u][1]]+1))。
现在就变成了一道纯数据结构题。要求在笛卡尔树上，维护一个序列h，每次可以单点修改，或者查询总体的(h[u]*(sz[c[u][0]]+1)(sz[c[u][1]]+1))的和。
但是单靠笛卡尔树无法修改啊？并不是，其实笛卡尔树本身“兼容”插入删除等操作，因为它的结构和Treap一模一样，Treap中的权值对应笛卡尔树中的key（本题中key是行编号），优先级对应val（本题中是h）。Treap中的insert，remove函数（或者FHQ Treap中的split,merge）笛卡尔树同样能用。
怎么修改呢？相当于把某一个点拿出来并从树中删掉，修改它的值，再重新加进树里去。如果用FHQ Treap的话，就相当于把某一个点和它前后全部拆开，修改它的值，再和它前后全部merge起来。
总时间复杂度(O(n log n + C log R))。
代码
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define In inline
#define ll long long
const int L = 40000;
const int N = 100000;
typedef pair<ll,ll>pll;
In ll read(){
ll s = 0,ww = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')ww = -1;ch = getchar();}
while('0' <= ch && ch <= '9'){s = 10 * s + ch - '0';ch = getchar();}
return s * ww;
}
int n;
ll R,C;
struct CartTree{
int cnt,rt;
int c[N+5][2],val[N+5],pri[N+5]; //val即第几列，pri即h
ll sz[N+5],sum[N+5];
int create(int x){
cnt++;
val[cnt] = x;
pri[cnt] = 0; //初始h都为0
sz[cnt] = 1;
return cnt;
}
void pushup(int u){
int lc = c[u][0],rc = c[u][1];
sz[u] = sz[lc] + sz[rc] + 1;
sum[u] = sum[lc] + sum[rc] + pri[u] * (sz[lc] + 1) * (sz[rc] + 1);
}
int build(int l,int r){
if(l == r)return create(l);
int m = (l + r) >> 1;
int u = create(m);
if(l <= m - 1)c[u][0] = build(l,m - 1);
if(m + 1 <= r)c[u][1] = build(m + 1,r);
pushup(u);
return u;
}
int merge(int u,int v){
if(!u || !v)return u + v;
if(pri[u] > pri[v]){
c[u][1] = merge(c[u][1],v);
pushup(u);
return u;
}
else{
c[v][0] = merge(u,c[v][0]);
pushup(v);
return v;
}
}
void split(int u,int x,int &v,int &w){
if(!u)v = w = 0;
else{
if(val[u] <= x){
v = u;
split(c[v][1],x,c[v][1],w);
}
else{
w = u;
split(c[w][0],x,v,c[w][0]);
}
pushup(u);
}
}
void ud(int i,int x){ //将h[i]修改为x
int u,v,w;
split(rt,i,u,w);
split(u,i - 1,u,v);
pri[v] = x;
pushup(v);
rt = merge(merge(u,v),w);
}
ll query(){
return sum[rt];
}
}T;
pll p[N+5];
int main(){
R = read();C = read();n = read();
for(rg int i = 1;i <= n;i++){
p[i].second = read(),p[i].first = read();
}
T.rt = T.build(1,R);
sort(p + 1,p + n + 1);
int cur = 0;
ll ans = 0;
for(rg ll cury = 1;cury <= C;cury++){
while(cur < n && p[cur+1].first == cury){
cur++;
T.ud(p[cur].second,cury);
}
ans += cury * R * (R + 1) / 2;
ans -= T.query();
}
ans = R * (R + 1) / 2 * C * (C + 1) / 2 - ans;
cout << ans << endl;
return 0;
}