题面
题解
现场得分：100/100
这道题我当场写了一个(O(Rnklog n))的东西。过了。
事情是如果枚举一条边界之后，倒序处理就能用链表，但是我是正序处理的，就只能用set。
下发题解
- 应该是dwh写的
代码
我的卡常代码
#include<bits/stdc++.h>
#define LL long long
#define MAXN 3010
using namespace std;
template<typename T>void Read(T &cn)
{
char c; int sig = 1;
while(!isdigit(c = getchar())) if(c == '-') sig = -1; cn = c-48;
while(isdigit(c = getchar())) cn = cn*10+c-48; cn*=sig;
}
template<typename T>void Write(T cn)
{
if(cn < 0) {putchar('-'); cn = 0-cn; }
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
while(cn) wei++, cm = cm*10+cn%10, cn/=10;
while(wei--) putchar(cm%10+48), cm /= 10;
putchar(cx+48);
}
template<typename T>void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
template<typename T>void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
struct qwe{
int x,y;
void getit() {Read(x); Read(y); }
inline friend bool operator <(qwe a, qwe b) {return a.x == b.x ? a.y < b.y : a.x < b.x; }
};
struct qwer{
int wei, num;
void mk(int cn, int cm) {wei = cn; num = cm; }
inline friend bool operator <(qwer a, qwer b) {return a.wei == b.wei ? a.num < b.num : a.wei < b.wei; }
};
int R,C,n,k;
qwe a[MAXN+1];
int wei1[12], wei2[12];
int wlen1, wlen2;
set<qwer> S;
typedef set<qwer>::iterator IT;
LL ans, zong;
void zeng(int cn, int cm)
{
// printf("in zeng : cn = %d cm = %d
",cn,cm);
qwer lin; lin.mk(cn, cm);
IT lin1 = S.upper_bound(lin);
wlen1 = wlen2 = 0;
for(IT i = lin1;i != S.end() && wlen2 < k;i++) wei2[++wlen2] = i->wei;
if(lin1 != S.begin()) {
lin1--;
for(IT i = lin1;i != S.begin() && wlen1 < k;i--) wei1[++wlen1] = i->wei;
if(wlen1 < k && S.begin() != S.end()) wei1[++wlen1] = (S.begin())->wei;
}
if(wlen1 < k) wei1[++wlen1] = 0;
if(wlen2 < k) wei2[++wlen2] = C+1;
// for(int i = 0;i<=wlen1;i++) printf("%d ",wei1[i]); puts("");
// for(int i = 0;i<=wlen2;i++) printf("%d ",wei2[i]); puts("");
wei1[0] = wei2[0] = cn;
for(int i = k-wlen1+1;i<=wlen2;i++) zong = 1ll*(wei2[i]-wei2[i-1])*(wei1[k-i]-wei1[k+1-i]) + zong;
S.insert(lin);
}
int main()
{
// freopen("rectangle.in","r",stdin);
// freopen("rectangle.out","w",stdout);
Read(R); Read(C); Read(n); Read(k);
for(int i = 1;i<=n;i++) a[i].getit();
sort(a+1, a+n+1); ans = 0;
LL lsta = 0, lstx = -1;
for(int i = 1;i<=R;i++)
{
int xian = 0;
while(xian <= n && a[xian+1].x < i) xian++;
if(lstx == xian) {ans = ans + lsta; continue; }
lsta = 0; lstx = xian;
zong = 0; S.clear();
for(int j = i;j<=R;j++)
{
while(xian < n && a[xian+1].x <= j) {xian++; zeng(a[xian].y, xian); }
lsta = lsta + zong;
}
ans = ans + lsta;
}
Write(ans); puts("");
return 0;
}
题解代码
# include <bits/stdc++.h>
using namespace std;
namespace Base{
# define mr make_pair
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const ll infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
template<typename T> void read(T &x){
x = 0; int fh = 1; double num = 1.0; char ch = getchar();
while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
if (ch == '.'){
ch = getchar();
while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
}
x = x * fh;
}
template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;
const int N = 3010;
struct Node{
int x, y;
}p[N];
int L, C, n, k, cnt[N], nxt[N], pre[N], num[N], les[N], hav[N];
ll ans;
bool cmp(Node x, Node y){
return x.x < y.x || (x.x == y.x && x.y < y.y);
}
void recal(int x){
num[x] = (x - pre[x] - 1) * (x - pre[x]) / 2;
int w = (x - pre[x]);
while (les[x] != C + 1 && hav[x] < k){
les[x] = nxt[les[x]];
hav[x] += cnt[les[x]];
}
num[x] = num[x] + w * (les[x] - x);
}
int main(){
freopen("rectangle.in", "r", stdin);
freopen("rectangle.out", "w", stdout);
read(L); read(C); read(n); read(k);
for (int i = 1; i <= n; i++){
read(p[i].x); read(p[i].y);
}
sort(p + 1, p + n + 1, cmp);
for (int i = 1; i <= L; i++){
memset(cnt, 0, sizeof(cnt));
for (int j = n; j >= 1; j--){
if (p[j].x < i) break;
cnt[p[j].y]++;
}
int nt = C + 1;
for (int j = C; j >= 1; j--)
if (cnt[j] > 0) nxt[j] = nt, pre[nt] = j, nt = j;
pre[nt] = 0; nxt[0] = nt; nxt[C + 1] = C + 2;
int tot = C * (C + 1) / 2, non = 0;
for (int j = nxt[0]; j != C + 2; j = nxt[j]){
les[j] = j, hav[j] = cnt[j];
recal(j);
non = non + num[j];
}
ans = ans + tot - non;
for (int t = L - 1, j = n; t >= i; t--){
while (p[j].x > t){
--cnt[p[j].y];
int q = p[j].y, l = cnt[p[j].y];
while (q != 0 && les[q] >= p[j].y){
non = non - num[q];
hav[q]--;
recal(q);
non = non + num[q];
q = pre[q]; l = l + cnt[q];
}
if (cnt[p[j].y] == 0){
nxt[pre[p[j].y]] = nxt[p[j].y];
pre[nxt[p[j].y]] = pre[p[j].y];
recal(nxt[p[j].y]);
}
j--;
}
ans = ans + tot - non;
}
}
printf("%lld
", ans);
return 0;
}