ZillionX 大战简单题
ZillionX
·
·
个人记录
前传
P4416
二维矩形数颜色，但是只有分离和包含关系。
# 第一回合
ZillionX 使用传统艺能「扫描线」，将问题转化为了：
> 给你 $n$ 个只有分离和包含关系的区间，对每个点找出最小的包含它的区间。
ZillionX 看着这个问题，脑海中闪出了曾经的回忆：那是点分治最辉煌的那一刹那，ZillionX 曾拜倒于点分脚下，与模拟赛 T1 大战三百回合，最后铩羽而归。
具体的讲，你考虑这样一件事，就是说：维护一个 ```pair<int,int> set```，然后很容易对二分找出这个区间。然后给矩形建树，对每个结点维护一个颜色集合，启发式合并一下很容易做到 $\rm poly \log$。
ZillionX 耗时 1h 写出了 4KB 大代码：
```cpp
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define LL long long
#define bg begin
#define ed end
#define pb push_back
#define clr clear
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define ins insert
#define ers erase
#define lb lower_bound
#define ub upper_bound
#define rvs reverse
#define btc __builtin_popcount
#define umap unordered_map
#define str string
#define gtl getline
using namespace std;
const int N=8e5+5;
int n,m,tn,dc[N],ans[N];
vector<pair<pi,pi>> jx[N];
vector<pi> sb[N];
vector<int> g[N];
set<int> co[N];
struct sq {
int xl,yl,xr,yr;
}a[N];
struct qus {
int x,y,c;
}qs[N];
set<pair<pi,int>> s;
void mrg(set<int> x,set<int> y) {
if (x.size()<y.size()) swap(x,y);
for (auto v:y) x.ins(v);
}
void dfs(int u) {
for (int v:g[u]) {
dfs(v);
mrg(co[u],co[v]);
}
ans[u]=co[u].size();
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) {
int aa,b,c,d;
scanf("%d%d%d%d",&aa,&b,&c,&d);
c++;
a[i]=(sq){aa,b,c,d};
dc[++tn]=aa,dc[++tn]=b,dc[++tn]=c,dc[++tn]=d;
}
for (int i=1;i<=m;i++) {
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
qs[i]=(qus){x,y,c};
dc[++tn]=x,dc[++tn]=y;
}
sort(dc+1,dc+tn+1);
tn=unique(dc+1,dc+tn+1)-dc-1;
int mxv=tn;
for (int i=1;i<=n;i++) {
a[i].xl=lb(dc+1,dc+tn+1,a[i].xl)-dc;
a[i].yl=lb(dc+1,dc+tn+1,a[i].yl)-dc;
a[i].xr=lb(dc+1,dc+tn+1,a[i].xr)-dc;
a[i].yr=lb(dc+1,dc+tn+1,a[i].yr)-dc;
// printf("%d %d\n",a[i].yl,a[i].yr);
jx[a[i].xl].pb(mp(mp(a[i].yl,a[i].yr),mp(0,i)));
jx[a[i].xr].pb(mp(mp(a[i].yl,a[i].yr),mp(1,i)));
}
for (int i=1;i<=m;i++) {
qs[i].x=lb(dc+1,dc+tn+1,qs[i].x)-dc;
qs[i].y=lb(dc+1,dc+tn+1,qs[i].y)-dc;
sb[qs[i].x].pb(mp(qs[i].y,qs[i].c));
}
int rt=n+1;
s.ins(mp(mp(1e9,1e9),1e9));
for (int i=1;i<=mxv;i++) {
for (auto u:jx[i])
if (u.se.fi==1) s.ers(mp(mp(u.fi.fi,u.fi.se),u.se.se));
for (auto u:jx[i])
if (u.se.fi==0) {
auto p=s.ub(mp(mp(u.fi.fi,u.fi.se),0));
if (p==s.bg() || s.size()==1) {
g[rt].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
continue;
}
p--;
if ((*p).fi.se<u.fi.fi) {
g[rt].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
continue;
}
// printf("%d\n",u.se.se);
g[(*p).se].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
}
for (auto u:sb[i]) {
auto p=s.ub(mp(mp(u.fi,u.fi),0));
// printf("%d %d\n",u.fi,u.fi);
// for (auto v:s) printf("%d %d\n",v.fi.fi,v.fi.se);
if (p==s.bg() || s.size()==1) continue;
p--;
// printf("%d %d\n",(*p).fi.fi,(*p).fi.se);
if ((*p).fi.se<u.fi) continue;
co[(*p).se].ins(u.se);
}
}
// for (int i=1;i<=n;i++) printf("%d\n",co[i].size());
for (int v:g[rt]) dfs(v);
for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
```
随便捏了一组数据发现假了。ZillionX 感到有点寄。
# 第二回合
观察这组数据，ZillionX 发现对于每个点，只找左端点最接近的集合是不行的，所以就建了一个按右端点排序的集合。
ZillionX 开始给算法打补丁。
ZillionX 灵机一动，要是插入顺序不同的话，似乎会影响程序的运行结果。
于是 ZillionX 把右端点的符号改成了负（保证左端点相同时先插右端点大的），加了个 ```sort(jx[i].bg(),jx[i].ed());```。
现在代码成了这个样子。
```cpp
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define LL long long
#define bg begin
#define ed end
#define pb push_back
#define clr clear
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define ins insert
#define ers erase
#define lb lower_bound
#define ub upper_bound
#define rvs reverse
#define btc __builtin_popcount
#define umap unordered_map
#define str string
#define gtl getline
using namespace std;
const int N=8e5+5;
int n,m,tn,dc[N],ans[N];
vector<pair<pi,pi>> jx[N];
vector<pi> sb[N];
vector<int> g[N];
set<int> co[N];
struct sq {
int xl,yl,xr,yr;
}a[N];
struct qus {
int x,y,c;
}qs[N];
set<pair<pi,int>> s,sf;
void mrg(set<int> &x,set<int> &y) {
if (x.size()<y.size()) swap(x,y);
for (auto v:y) x.ins(v);
}
void dfs(int u) {
for (int v:g[u]) {
dfs(v);
mrg(co[u],co[v]);
}
ans[u]=co[u].size();
}
bool isin(pi x,pi y) {
y.fi=abs(y.fi),y.se=abs(y.se);
if (y.fi>y.se) swap(y.fi,y.se);
x.fi=abs(x.fi),x.se=abs(x.se);
if (x.fi>x.se) swap(x.fi,x.se);
return x.fi<=y.fi && y.se<=x.se;
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) {
int aa,b,c,d;
scanf("%d%d%d%d",&aa,&b,&c,&d);
c++;
a[i]=(sq){aa,b,c,d};
dc[++tn]=aa,dc[++tn]=b,dc[++tn]=c,dc[++tn]=d;
}
for (int i=1;i<=m;i++) {
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
qs[i]=(qus){x,y,c};
dc[++tn]=x,dc[++tn]=y;
}
sort(dc+1,dc+tn+1);
tn=unique(dc+1,dc+tn+1)-dc-1;
int mxv=tn;
for (int i=1;i<=n;i++) {
a[i].xl=lb(dc+1,dc+tn+1,a[i].xl)-dc;
a[i].yl=lb(dc+1,dc+tn+1,a[i].yl)-dc;
a[i].xr=lb(dc+1,dc+tn+1,a[i].xr)-dc;
a[i].yr=lb(dc+1,dc+tn+1,a[i].yr)-dc;
jx[a[i].xl].pb(mp(mp(a[i].yl,-a[i].yr),mp(0,i)));
jx[a[i].xr].pb(mp(mp(a[i].yl,-a[i].yr),mp(1,i)));
}
for (int i=1;i<=m;i++) {
qs[i].x=lb(dc+1,dc+tn+1,qs[i].x)-dc;
qs[i].y=lb(dc+1,dc+tn+1,qs[i].y)-dc;
sb[qs[i].x].pb(mp(qs[i].y,qs[i].c));
}
int rt=n+1;
s.ins(mp(mp(1e9,1e9),1e9));
sf.ins(mp(mp(1e9,1e9),1e9));
for (int i=1;i<=mxv;i++) {
sort(jx[i].bg(),jx[i].ed());
for (auto u:jx[i])
if (u.se.fi==1) {
s.ers(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ers(mp(mp(u.fi.se,u.fi.fi),u.se.se));
}
for (auto u:jx[i])
if (u.se.fi==0) {
auto p=s.ub(mp(mp(u.fi.fi,1e9),0));
auto p2=sf.ub(mp(mp(u.fi.se,1e9),0));
if (p==s.bg()) {
if (p2==sf.bg()) {
g[rt].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ins(mp(mp(u.fi.se,u.fi.fi),u.se.se));
continue;
}
p2--;
if (!isin((*p2).fi,u.fi)) {
g[rt].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ins(mp(mp(u.fi.se,u.fi.fi),u.se.se));
continue;
}
g[(*p2).se].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ins(mp(mp(u.fi.se,u.fi.fi),u.se.se));
continue;
}
p--;
if (!isin((*p).fi,u.fi)) {
if (p2==sf.bg()) {
g[rt].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ins(mp(mp(u.fi.se,u.fi.fi),u.se.se));
continue;
}
p2--;
if (!isin((*p2).fi,u.fi)) {
g[rt].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ins(mp(mp(u.fi.se,u.fi.fi),u.se.se));
continue;
}
g[(*p2).se].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ins(mp(mp(u.fi.se,u.fi.fi),u.se.se));
continue;
}
g[(*p).se].pb(u.se.se);
s.ins(mp(mp(u.fi.fi,u.fi.se),u.se.se));
sf.ins(mp(mp(u.fi.se,u.fi.fi),u.se.se));
continue;
}
for (auto u:sb[i]) {
auto p=s.ub(mp(mp(u.fi,1e9),0));
auto p2=sf.ub(mp(mp(-u.fi,1e9),0));
if (p==s.bg()) {
if (p2==sf.bg()) continue;
p2--;
if (!isin((*p2).fi,mp(u.fi,u.fi))) continue;
co[(*p2).se].ins(u.se);
continue;
}
else {
p--;
if (!isin((*p).fi,mp(u.fi,u.fi))) {
if (p2==sf.bg()) continue;
p2--;
if (!isin((*p2).fi,mp(u.fi,u.fi))) continue;
co[(*p2).se].ins(u.se);
continue;
}
co[(*p).se].ins(u.se);
continue;
}
}
}
for (int v:g[rt]) dfs(v);
for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
```
很漂亮对吧？实际上这玩意只有 20pts。
# 第三回合
ZillionX 发现手玩数据太烦了。所以他先写了个暴力。
```cpp
#include <bits/stdc++.h>
#define ins insert
using namespace std;
const int N=8e4+5;
int n,m,o[300][300];
struct sq {
int xl,yl,xr,yr;
}a[N];
set<int> co[N];
int main() {
// freopen("sj.txt","r",stdin);
// freopen("force.txt","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) {
int aa,b,c,d;
scanf("%d%d%d%d",&aa,&b,&c,&d);
for (int x=aa;x<=c;x++)
for (int y=b;y<=d;y++)
o[x][y]=i;
a[i]=(sq){aa,b,c,d};
}
// for (int i=1;i<=10;i++) {
// for (int j=1;j<=10;j++)
// printf("%d ",o[i][j]);
// printf("\n");
// }
for (int i=1;i<=m;i++) {
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
for (int i=1;i<=n;i++) {
if (a[i].xl<=x && x<=a[i].xr && a[i].yl<=y && y<=a[i].yr)
co[i].ins(c);
}
}
for (int i=1;i<=n;i++) printf("%d\n",co[i].size());
return 0;
}
```
（这玩意甚至能拿 33pts）
然后 ZillionX 发现手捏数据也太烦了，就写了个 data maker：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=1e3;
int m=5;
struct sq {
int xl,yl,xr,yr;
}a[N];
int main() {
srand(time(0));
// freopen("sj.txt","w",stdout);
int tn=0;
for (int i=1;tn<=5;i++) {
int aa=rand()%10+1,b=rand()%10+1,c=rand()%10+1,d=rand()%10+1;
if (aa>c) swap(aa,c);
if (b>d) swap(b,d);
int fl=1;
for (int j=1;j<=tn;j++) {
if ((a[j].xl<=aa && a[j].yl<=b && c<=a[j].xr && d<=a[j].yr) || (aa>a[j].xr || b>a[j].yr)) continue;
else {
fl=0;
break;
}
}
if (!fl) continue;
a[++tn]=(sq){aa,b,c,d};
}
printf("%d %d\n",tn,m);
for (int i=1;i<=tn;i++) {
printf("%d %d %d %d\n",a[i].xl,a[i].yl,a[i].xr,a[i].yr);
}
for (int i=1;i<=m;i++) {
int x=rand()%10+1,y=rand()%10+1,c=rand()%10+1;
printf("%d %d %d\n",x,y,c);
}
return 0;
}
```
他甚至还顺手写了个对拍（他真的好温柔啊，我哭死）。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
ll ret=0;char ch=' ',c=getchar();
while(!(c<='9'&&c>='0')) ch=c,c=getchar();
while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ch=='-'?-ret:ret;
}
int main()
{
for(int i=1;i<=1000;i++)
{
system("data.exe>data.txt");
system("chj.exe<data.txt>chj.txt");
double st=clock();
system("force.exe<data.txt>force.txt");
double ed=clock();
if(system("fc chj.txt force.txt")) {printf("WA\n");break;}
else printf("AC #%d Time:%.3lfms\n",i,ed-st);
}
return 0;
}
```
~~或许是女主给我们的男主 ZillionX 的祈祷起了作用~~，不对女主还没出场，ZillionX 发现了一组 hack 数据：
```cpp
6 5
1 1 3 5
5 6 10 10
5 7 7 9
9 7 10 8
9 7 10 8
9 10 10 10
4 2 7
9 5 5
1 4 5
8 4 7
9 9 1
```
然后你就会很震撼的发现，这组数据里面的某个点居然不满足二分出左右端点最接近的区间就可以插入这个最重要的条件。
ZillionX 崩溃了。
假了 inf 个算法之后，ZillionX 坚信打补丁的算法全是假的。
寄。
# 第四回合
ZillionX 突然不想写这题了。
~~但是女主告诉他不能摆烂。~~
所以 ZillionX 准备换一种写法。
线段树覆盖区间似乎是个不错的选择，但是在撤销操作时需要找出最早的没有被撤销的父亲，才能正确地覆盖掉区间。
ZillionX 两眼一黑，双腿一蹬，准备直接莽可以被 hack 掉的线段树写法。
10min 过去了，他写完了（可以看出我们的男主的手速很快）。
发现有点小问题，对拍了一下，把错误改回来，直接交了。
```cpp
#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
#define LL long long
#define bg begin
#define ed end
#define pb push_back
#define clr clear
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
#define ins insert
#define ers erase
#define lb lower_bound
#define ub upper_bound
#define rvs reverse
#define btc __builtin_popcount
#define umap unordered_map
#define str string
#define gtl getline
using namespace std;
const int N=8e5+5;
int n,m,tn,dc[N],ans[N],f[N];
vector<pair<pi,pi>> jx[N];
vector<pi> sb[N];
vector<int> g[N];
set<int> co[N];
bool e[N];
struct sq {
int xl,yl,xr,yr;
}a[N];
struct qus {
int x,y,c;
}qs[N];
void mrg(set<int> &x,set<int> &y) {
if (x.size()<y.size()) swap(x,y);
for (auto v:y) x.ins(v);
}
void dfs(int u) {
for (int v:g[u]) {
dfs(v);
mrg(co[u],co[v]);
}
ans[u]=co[u].size();
}
int v[N*4],t[N*4];
#define ls (x<<1)
#define rs (x<<1|1)
void up(int x) {
if (v[ls]==v[rs]) v[x]=v[ls];
}
void dn(int x) {
if (!t[x]) return;
v[ls]=v[rs]=t[ls]=t[rs]=t[x];
t[x]=0;
}
void upd(int x,int l,int r,int L,int R,int k,int pr) {
// if (pr==6) {
// printf("%d %d %d\n",l,r,v[x]);
// }
if (L<=l && r<=R) {if (v[x] && v[x]!=pr) return;
v[x]=t[x]=k;
return;
}
dn(x);
int mid=(l+r)>>1;
if (L<=mid) upd(ls,l,mid,L,R,k,pr);
if (R>mid) upd(rs,mid+1,r,L,R,k,pr);
up(x);
}
void mof(int x,int l,int r,int L,int R,int k) {
if (L<=l && r<=R) {
v[x]=t[x]=k;
return;
}
dn(x);
int mid=(l+r)>>1;
if (L<=mid) mof(ls,l,mid,L,R,k);
if (R>mid) mof(rs,mid+1,r,L,R,k);
up(x);
}
int qry(int x,int l,int r,int p) {
if (l==r) return v[x];
dn(x);
int mid=(l+r)>>1;
if (p<=mid) return qry(ls,l,mid,p);
return qry(rs,mid+1,r,p);
}
int fg(int x) {
x=f[x];
while (x && e[x]) x=f[x];
return x;
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) {
int aa,b,c,d;
scanf("%d%d%d%d",&aa,&b,&c,&d);
c++;
a[i]=(sq){aa,b,c,d};
dc[++tn]=aa,dc[++tn]=b,dc[++tn]=c,dc[++tn]=d;
}
for (int i=1;i<=m;i++) {
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
qs[i]=(qus){x,y,c};
dc[++tn]=x,dc[++tn]=y;
}
sort(dc+1,dc+tn+1);
tn=unique(dc+1,dc+tn+1)-dc-1;
int mxv=tn;
for (int i=1;i<=n;i++) {
a[i].xl=lb(dc+1,dc+tn+1,a[i].xl)-dc;
a[i].yl=lb(dc+1,dc+tn+1,a[i].yl)-dc;
a[i].xr=lb(dc+1,dc+tn+1,a[i].xr)-dc;
a[i].yr=lb(dc+1,dc+tn+1,a[i].yr)-dc;
jx[a[i].xl].pb(mp(mp(a[i].yl,-a[i].yr),mp(0,i)));
jx[a[i].xr].pb(mp(mp(a[i].yl,-a[i].yr),mp(1,i)));
}
for (int i=1;i<=m;i++) {
qs[i].x=lb(dc+1,dc+tn+1,qs[i].x)-dc;
qs[i].y=lb(dc+1,dc+tn+1,qs[i].y)-dc;
sb[qs[i].x].pb(mp(qs[i].y,qs[i].c));
}
int rt=n+1;
for (int i=1;i<=mxv;i++) {
sort(jx[i].bg(),jx[i].ed());
for (auto u:jx[i])
if (u.se.fi==1) {
e[u.se.se]=1;
// if (u.se.se==6) printf("%d\n",fg(u.se.se));
upd(1,1,mxv,u.fi.fi,-u.fi.se,fg(u.se.se),u.se.se);
}
for (auto u:jx[i])
if (u.se.fi==0) {
int t=qry(1,1,mxv,u.fi.fi);
if (!t) t=n+1;
f[u.se.se]=t;
g[t].pb(u.se.se);
mof(1,1,mxv,u.fi.fi,-u.fi.se,u.se.se);
}
for (auto u:sb[i]) co[qry(1,1,mxv,u.fi)].ins(u.se);
}
for (int v:g[rt]) dfs(v);
for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
```
然后，，，就过了？！……
假的吧。
ZillionX 感到很无语。
# 后记
欢迎大家来 hack 我的程序。
~~其实我可以改成复杂度正确的只是懒得改。~~
# 总结
狗都不用 set，线段树什么的最好写了。