NC20501. [ZJOI2012]小蓝的好友(MRX)
描述
输入描述
每个输入文件中仅包含一个测试数据。
第一行包含两个由空格隔开的正整数R,C,N，表示游戏在一块[1,R]X[1,C]的地图上生成了N个资源点。
接下来有N行，每行包含两个整数 x,y，表示这个资源点的坐标
(1 ≤ x ≤ R,1 ≤ Y ≤ c)。
输出描述
输出文件应仅包含一个整数，表示至少包含一个资源点的区域的数量。具体的说，设N个资源点的坐标为(i=1..n),你需要计算有多少个四元组(LB,DB,RB,UB)满足1 ≤ LB ≤ RB ≤ R,1 ≤ DB ≤ UB ≤ C，且存在一个i使得LB ≤ Xi ≤ RB,DB ≤ Yi ≤ UB均成立。
示例1
输入:
5 5 4 1 2 2 3 3 5 4 1
输出:
139
C++(clang++11) 解法, 执行用时: 90ms, 内存消耗: 12152K, 提交时间: 2021-02-14 14:20:42
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 400010;
int n, m, q;
ll ans = 0, sum = 0;
vector<int> e[N];
int ch[2][N], sz[N], dep[N], fa[N], tot, rt; ll val[N];
int sta[N], top;
void update(int u) {
if(!u) return ;
sz[u] = 1;
if(ch[0][u]) sz[u] += sz[ch[0][u]]; if(ch[1][u]) sz[u] += sz[ch[1][u]];
sum -= val[u];
val[u] = (ll)sz[u] * (sz[u] + 1) / 2 * (dep[fa[u]] - dep[u]);
sum += val[u];
}
void build(int &u, int ff, int l, int r) {
u = (l + r) >> 1, fa[u] = ff;
if(l < u) build(ch[0][u], u, l, u - 1);
if(u < r) build(ch[1][u], u, u + 1, r);
update(u);
}
void insert(int u) {
top = 0, dep[u] = tot;
for(; dep[u] > dep[fa[u]];) {
int y = fa[u], z = fa[y], k = ch[1][y] == u, w = ch[k ^ 1][u];
ch[ch[1][z] == y][z] = u; ch[k][y] = w, ch[k ^ 1][u] = y;
fa[w] = y; fa[u] = z, fa[y] = u;
sta[++top] = y;
}
sta[++top] = u;
for(int i = 1; i <= top; i++) {
update(sta[i]);
if(ch[0][sta[i]]) update(ch[0][sta[i]]);
if(ch[1][sta[i]]) update(ch[1][sta[i]]);
}
}
int main() {
scanf("%d%d%d", &n, &m, &q), build(ch[1][rt], 0, 1, m);
ans = (ll)n * (n + 1) / 2 * m * (m + 1) / 2;
for(int i = 1, x, y; i <= q; i++) scanf("%d%d", &x, &y), e[x].pb(y);
for(int i = 1; i <= n; i++) {
++tot, ++dep[rt];
if(ch[0][rt]) update(ch[0][rt]); if(ch[1][rt]) update(ch[1][rt]);
for(int j = 0; j < e[i].size(); j++) insert(e[i][j]);
ans -= sum;
}
printf("%lld\n", ans);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 150ms, 内存消耗: 12152K, 提交时间: 2019-05-06 09:08:01
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 400010;
int n, m, q;
ll ans = 0, sum = 0;
vector<int> e[N];
int ch[2][N], sz[N], dep[N], fa[N], tot, rt; ll val[N];
int sta[N], top;
void update(int u) {
if(!u) return ;
sz[u] = 1;
if(ch[0][u]) sz[u] += sz[ch[0][u]]; if(ch[1][u]) sz[u] += sz[ch[1][u]];
sum -= val[u];
val[u] = (ll)sz[u] * (sz[u] + 1) / 2 * (dep[fa[u]] - dep[u]);
sum += val[u];
}
void build(int &u, int ff, int l, int r) {
u = (l + r) >> 1, fa[u] = ff;
if(l < u) build(ch[0][u], u, l, u - 1);
if(u < r) build(ch[1][u], u, u + 1, r);
update(u);
}
void insert(int u) {
top = 0, dep[u] = tot;
for(; dep[u] > dep[fa[u]];) {
int y = fa[u], z = fa[y], k = ch[1][y] == u, w = ch[k ^ 1][u];
ch[ch[1][z] == y][z] = u; ch[k][y] = w, ch[k ^ 1][u] = y;
fa[w] = y; fa[u] = z, fa[y] = u;
sta[++top] = y;
}
sta[++top] = u;
for(int i = 1; i <= top; i++) {
update(sta[i]);
if(ch[0][sta[i]]) update(ch[0][sta[i]]);
if(ch[1][sta[i]]) update(ch[1][sta[i]]);
}
}
int main() {
scanf("%d%d%d", &n, &m, &q), build(ch[1][rt], 0, 1, m);
ans = (ll)n * (n + 1) / 2 * m * (m + 1) / 2;
for(int i = 1, x, y; i <= q; i++) scanf("%d%d", &x, &y), e[x].pb(y);
for(int i = 1; i <= n; i++) {
++tot, ++dep[rt];
if(ch[0][rt]) update(ch[0][rt]); if(ch[1][rt]) update(ch[1][rt]);
for(int j = 0; j < e[i].size(); j++) insert(e[i][j]);
ans -= sum;
}
printf("%lld\n", ans);
return 0;
}