Codeforces Round #666
前言
感觉我补题速度好慢。。
上大学后，因为不存在停课，能分给acm的时间还是挺少的。。
然而我效率总是提不上来。。唉。。。。
A to C 略
D Rainbow Rectangles
题意
一个边长为(L)的正方形网格上，有(n)颗糖，第(i)颗糖所在位置为((xi+0.5,yi+0.5)),每颗糖都有颜色，颜色一共有(K)种，问有多少端点在整点上的矩形包含了所有的颜色，即在这种矩阵中，每种颜色的糖至少出现一次。(0leq K leq n leq 2000，1leq Lleq {10}^{9}) 。
题解
首先肯定离散化。
如果是一维上的话，我们用双指针就是(O(n))的做法。
转换到两维平面上，显然枚举左右端点，然后中间用一维的方法就得到了(O(n^3))的做法。
然而这肯定不行。。考虑怎么压掉一个n。
我们考虑在枚举左右端点时，能否快速得到中间部分的答案。
左端点肯定是从左向右，这时候右端点有两种枚举方法：从左向右，从右向左。
向右的话我们需要维护增加的点，新增的点的贡献很难算。。
向左的话，我们需要维护删点的操作。我们可以维护每个点颜色相同的左边高度比它高的最低点u，以及比它低的最高点d。（这里要用到链表）
然后删点时我们用u来更新d上方的所有点，这个操作可以用线段树。然后就能快速统计答案了。。。
(Code)
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e3+10;
const LL mod=1e9+7;
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void print(LL x){
if(x>9) print(x/10);
putchar(x%10+'0');
}
struct link{
int L[N],R[N];
void del(int x){
R[L[x]]=R[x];
L[R[x]]=L[x];
}
}S,s;
int n,K,L;
struct P{int x,y,c,ny;}a[N];
bool cmpx(P x,P y){return x.x<y.x;}
bool cmpy(P x,P y){return x.y<y.y;}
int sy[N],las[N];
#define ls ch[0]
#define rs ch[1]
int col[N];
int f[N],t[N];
struct node{
int l,r,mid;
int sum,mn,mx,lazy;
node *ch[2];
node(int x,int y):l(x),r(y),mid(l+r>>1),sum(0){
if(x<y){
ls=new node(x,mid);
rs=new node(mid+1,y);
}
else ls=rs=NULL;
}
void update(int c){
sum=1ll*(sy[r]-sy[l-1])*c%mod;
lazy=mn=mx=c;
}
void pushup(){
sum=(ls->sum+rs->sum)%mod;
mn=min(ls->mn,rs->mn);
mx=max(ls->mx,rs->mx);
}
void init(){
if(l==r){update(f[l]);return;}
ls->init();rs->init();lazy=0;
pushup();
}
void change(int x,int c){
if(mn>=c) return;
if(mx<=c&&l==x){
update(c);
return;
}
if(lazy){
if(ls) {
ls->update(lazy);
rs->update(lazy);
}
lazy=0;
}
if(x<=mid) ls->change(x,c);
rs->change(max(mid+1,x),c);
pushup();
}
}*root=NULL;
LL ans=0;
int main(){
scanf("%d%d%d",&n,&K,&L);
for(int i=1;i<=n;++i){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
}
sort(a+1,a+1+n,cmpy);
a[0].x=a[0].y=-1;a[n+1].x=a[n+1].y=L;
for(int i=0;i<=n+1;++i) {sy[i]=a[i].y;a[i].ny=i;}
for(int i=1;i<=n;++i){
int &it=las[a[i].c];
if(it) {s.R[it]=i;s.L[i]=it;}
s.R[i]=n+1;it=i;
}
sort(a+1,a+1+n,cmpx);
root=new node(1,n);
// cout<<"y"<<endl;
for(int i=1;i<=n;++i){
//cout<<i<<endl;
if(a[i].x!=a[i-1].x){
for(int j=0;j<i;++j) col[a[j].ny]=0;
for(int j=i;j<=n;++j) col[a[j].ny]=a[j].c;
for(int l=1,r=1,tot=0;l<=n;++l){
for(;r<=n&&tot<K;++r){
if(col[r]&&!t[col[r]]) ++tot;
t[col[r]]++;
}
f[l]=(tot<K?L:sy[r-1]);
--t[col[l]];
if(col[l]&&!t[col[l]]) --tot;
}
root->init();S=s;
for(int j=n;j>=1;j--){
ans+=1ll*(1ll*(sy[n]+1)*L%mod-root->sum+mod)%mod*(a[j+1].x-a[j].x)%mod*(a[i].x-a[i-1].x)%mod;
int p=a[j].ny;
root->change(S.L[p]+1,sy[S.R[p]]);
S.del(p);
}
}
s.del(a[i].ny);
}
ans=(ans%mod+mod)%mod;
cout<<ans<<endl;
return 0;
}
E Distance Matching
还没写QAQ