大模拟代码记录
CSP 赛事以为我能 30 分钟写出来 T3 于是我最后 30 分钟开始写 T3 然后没写完。然后 CSP 结束之后立刻开始做大模拟题。
删除了所有调试信息和注释。
P9754 [CSP-S 2023] 结构体
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+50;
int N;
string s,t,Na;
int CntStruct;
string NaYuan[205],NaSon[205][205];
map<string,int>StructId,SonId[205],Yuan;
int Cnt[MAXN];
struct Dot
{
int Id1;
long long a,s,Pos;
Dot(int _Id1,long long _a,long long _s,long long _Pos)
{
Id1=_Id1;
a=_a;
s=_s;
Pos=_Pos;
}
};
vector<Dot>Son[MAXN];
long long Len[MAXN],Size[MAXN];
long long ALLBegin;
long long sYuan[MAXN],aYuan[MAXN],tYuan[MAXN];
int CntYuan;
long long ans[MAXN];
int main()
{
StructId["byte"]=1;
Len[1]=Size[1]=1;
StructId["short"]=2;
Len[2]=Size[2]=2;
StructId["int"]=3;
Len[3]=Size[3]=4;
StructId["long"]=4;
Len[4]=Size[4]=8;
CntStruct=4;
cin>>N;
ALLBegin=0;
while(N--)
{
int op;
cin>>op;
if(op==1)
{
cin>>s;
StructId[s]=++CntStruct;
cin>>Cnt[CntStruct];
long long Begin=0;
for(int i=1;i<=Cnt[CntStruct];i++)
{
cin>>t>>Na;
NaSon[CntStruct][i-1]=Na;
if(i>1)
Begin=((Begin+Son[CntStruct].back().s-1)/Len[StructId[t]]+1)*Len[StructId[t]];
Son[CntStruct].push_back(Dot(StructId[t],Len[StructId[t]],Size[StructId[t]],Begin));
SonId[CntStruct][Na]=i-1;
Len[CntStruct]=max(Len[CntStruct],Len[StructId[t]]);
}
Size[CntStruct]=((Begin+Son[CntStruct].back().s-1)/Len[CntStruct]+1)*Len[CntStruct];
cout<<Size[CntStruct]<<" "<<Len[CntStruct]<<endl;
}
if(op==2)
{
cin>>t>>Na;
CntYuan++;
NaYuan[CntYuan]=Na;
Yuan[Na]=CntYuan;
tYuan[CntYuan]=StructId[t];
aYuan[CntYuan]=Len[tYuan[CntYuan]];
sYuan[CntYuan]=Size[tYuan[CntYuan]];
if(CntYuan>1)
{
ALLBegin=((ALLBegin+sYuan[CntYuan-1]-1)/aYuan[CntYuan]+1)*aYuan[CntYuan];
}
cout<<ALLBegin<<endl;
ans[CntYuan]=ALLBegin;
}
if(op==3)
{
cin>>s;
int NowId=0;
bool flag=false;
long long NowPos;
Na.clear();
for(int i=0;i<=s.length();i++)
{
if(i==s.length()||s[i]=='.')
{
if(flag==false)
{
NowId=Yuan[Na];
flag=true;
NowPos=ans[NowId];
NowId=tYuan[NowId];
}
else
{
int IdSon=SonId[NowId][Na];
Dot NowSon=Son[NowId][IdSon];
NowPos+=NowSon.Pos;
NowId=NowSon.Id1;
}
Na.clear();
}
else
{
Na.push_back(s[i]);
}
}
cout<<NowPos<<endl;
}
if(op==4)
{
long long NowPos;
cin>>NowPos;
int YuanId=0;
for(int i=1;i<=CntYuan;i++)
{
if(ans[i]>NowPos)
{
YuanId=i-1;
NowPos-=ans[i-1];
break;
}
}
if(YuanId==0)
{
YuanId=CntYuan;
NowPos-=ans[CntYuan];
}
string Nowans;
Nowans+=NaYuan[YuanId];
int ZiId=tYuan[YuanId];
bool flag=false;
while(true)
{
if(ZiId<=4)
{
if(NowPos>=0&&NowPos<Size[ZiId])
break;
}
if(NowPos>=Size[ZiId])
{
flag=true;
break;
}
bool Cut=false;
for(int i=0;i<Son[ZiId].size();i++)
{
if(Son[ZiId][i].Pos>NowPos)
{
Cut=true;
NowPos-=Son[ZiId][i-1].Pos;
Nowans+=".";
Nowans+=NaSon[ZiId][i-1];
ZiId=Son[ZiId][i-1].Id1;
break;
}
}
if(Cut==false)
{
NowPos-=Son[ZiId].back().Pos;
Nowans+=".";
Nowans+=NaSon[ZiId][Cnt[ZiId]-1];
ZiId=Son[ZiId].back().Id1;
}
}
if(flag)
puts("ERR");
else
cout<<Nowans<<endl;
}
}
}
P8216 [THUPC2022 初赛] 画图
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+50;
int N;
struct Line
{
int op,l,r,a;
Line(){}
Line(int _op,int _l,int _r,int _a)
{
op=_op;
l=_l;
r=_r;
a=_a;
}
}d[MAXN];
bool cmp1(Line a,Line b)
{
return a.a<b.a;
}
bool cmp2(Line a,Line b)
{
if(a.l==b.l)
return a.r>b.r;
return a.l<b.l;
}
int tot;
int G;
vector<Line>Vec[2],Temp,Group[20];
bool XiangJiao(Line a,Line b)
{
if(a.op==b.op)
{
return false;
}
if(b.l<=a.a&&a.a<=b.r&&a.l<=b.a&&b.a<=a.r)
return true;
return false;
}
void Read()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
{
int op,l,r,a;
scanf("%d%d%d%d",&op,&l,&r,&a);
Vec[op].push_back(Line(op,l,r,a));
}
}
void MergeSolve()
{
sort(Temp.begin(),Temp.end(),cmp2);
int Nowl=Temp[0].l,Nowr=Temp[0].r;
for(int i=1;i<Temp.size();i++)
{
if(Temp[i].l>Nowr)
{
d[++tot]=Line(Temp[0].op,Nowl,Nowr,Temp[0].a);
Nowl=Temp[i].l;
Nowr=Temp[i].r;
}
else
{
Nowr=max(Nowr,Temp[i].r);
}
}
d[++tot]=Line(Temp[0].op,Nowl,Nowr,Temp[0].a);
}
void Merge(int op)
{
sort(Vec[op].begin(),Vec[op].end(),cmp1);
for(int i=0;i<Vec[op].size();i++)
{
int j=i;
Temp.clear();
Temp.push_back(Vec[op][i]);
while(j+1<Vec[op].size()&&Vec[op][j+1].a==Vec[op][i].a)
{
j++;
Temp.push_back(Vec[op][j]);
}
MergeSolve();
i=j;
}
}
bool Check1()
{
if(tot!=15)
return false;
int Cnt=0;
for(int i=1;i<=tot;i++)
{
Cnt+=d[i].op;
}
if(Cnt!=8)
return false;
return true;
}
int father[MAXN];
int getfather(int x)
{
if(x!=father[x])
father[x]=getfather(father[x]);
return father[x];
}
bool vis[MAXN];
void Merge2()
{
for(int i=1;i<=tot;i++)
{
father[i]=i;
}
for(int Id=1;Id<=tot;Id++)
{
for(int i=1;i<=tot;i++)
{
if(i==Id)
continue;
if(XiangJiao(d[i],d[Id]))
{
int fx=getfather(i),fy=getfather(Id);
if(fx!=fy)
father[fy]=fx;
}
}
}
for(int i=1;i<=tot;i++)
{
bool flag=false;
for(int j=1;j<=tot;j++)
{
if(flag==false&&getfather(j)==i)
{
flag=true;
G++;
}
if(getfather(j)==i)
{
Group[G].push_back(d[j]);
}
}
}
}
int Id[10];
int Id2[10];
bool CheckT(vector<Line>Now)
{
if(Now.size()!=2)
return false;
for(int i=1;i<=2;i++)
Id2[i]=i;
while(true)
{
int I1=Id2[1]-1,I2=Id2[2]-1;
if(Now[I1].op==0
&&Now[I2].op==1
&&Now[I2].l<Now[I1].a
&&Now[I1].a==Now[I2].r
&&Now[I1].l<Now[I2].a
&&Now[I1].r>Now[I2].a
)
return true;
if(next_permutation(Id2+1,Id2+3)==false)
break;
}
return false;
}
bool CheckH(vector<Line>Now)
{
if(Now.size()!=3)
return false;
for(int i=1;i<=3;i++)
Id2[i]=i;
while(true)
{
int I3=Id2[1]-1,I4=Id2[2]-1,I5=Id2[3]-1;
if(Now[I3].op==1
&&Now[I4].op==0
&&Now[I5].op==1
&&Now[I3].l==Now[I5].l
&&Now[I5].l<Now[I4].a
&&Now[I4].a<Now[I3].r
&&Now[I3].r==Now[I5].r
&&Now[I3].a==Now[I4].l
&&Now[I4].l<Now[I4].r
&&Now[I4].r==Now[I5].a
)
return true;
if(next_permutation(Id2+1,Id2+4)==false)
break;
}
return false;
}
bool CheckU(vector<Line>Now)
{
if(Now.size()!=3)
return false;
for(int i=1;i<=3;i++)
Id2[i]=i;
while(true)
{
int I6=Id2[1]-1,I7=Id2[2]-1,I8=Id2[3]-1;
if(Now[I6].op==1
&&Now[I7].op==0
&&Now[I8].op==1
&&Now[I6].l==Now[I8].l
&&Now[I8].l==Now[I7].a
&&Now[I7].a<Now[I6].r
&&Now[I6].r==Now[I8].r
&&Now[I6].a==Now[I7].l
&&Now[I7].l<Now[I7].r
&&Now[I7].r==Now[I8].a
)
return true;
if(next_permutation(Id2+1,Id2+4)==false)
break;
}
return false;
}
bool CheckP(vector<Line>Now)
{
if(Now.size()!=4)
return false;
for(int i=1;i<=4;i++)
Id2[i]=i;
while(true)
{
int I9=Id2[1]-1,I10=Id2[2]-1,I11=Id2[3]-1,I12=Id2[4]-1;
if(Now[I9].op==1
&&Now[I10].op==0
&&Now[I11].op==0
&&Now[I12].op==1
&&Now[I9].l<Now[I11].a
&&Now[I11].a==Now[I12].l
&&Now[I12].l<Now[I9].r
&&Now[I9].r==Now[I10].a
&&Now[I10].a==Now[I12].r
&&Now[I9].a==Now[I10].l
&&Now[I10].l==Now[I11].l
&&Now[I11].l<Now[I10].r
&&Now[I10].r==Now[I11].r
&&Now[I11].r==Now[I12].a
)
return true;
if(next_permutation(Id2+1,Id2+5)==false)
break;
}
return false;
}
bool CheckC(vector<Line>Now)
{
if(Now.size()!=3)
return false;
for(int i=1;i<=3;i++)
Id2[i]=i;
while(true)
{
int I13=Id2[1]-1,I14=Id2[2]-1,I15=Id2[3]-1;
if(Now[I13].op==1
&&Now[I14].op==0
&&Now[I15].op==0
&&Now[I13].l==Now[I15].a
&&Now[I15].a<Now[I13].r
&&Now[I13].r==Now[I14].a
&&Now[I13].a==Now[I14].l
&&Now[I14].l==Now[I15].l
&&Now[I15].l<Now[I14].r
&&Now[I14].r==Now[I15].r
)
return true;
if(next_permutation(Id2+1,Id2+4)==false)
break;
}
return false;
}
bool Check3()
{
if(CheckT(Group[Id[1]])
&&CheckH(Group[Id[2]])
&&CheckU(Group[Id[3]])
&&CheckP(Group[Id[4]])
&&CheckC(Group[Id[5]])
)
return true;
return false;
}
int main()
{
Read();
Merge(0);
Merge(1);
if(Check1()==false)
{
puts("No");
return 0;
}
Merge2();
if(G>=6)
{
puts("No");
return 0;
}
for(int i=1;i<=5;i++)
{
Id[i]=i;
}
while(true)
{
if(Check3())
{
puts("Yes");
return 0;
}
if(next_permutation(Id+1,Id+6)==false)
break;
}
puts("No");
}
P3952 [NOIP2017 提高组] 时间复杂度
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e3+50;
int L;
char O[MAXN];
int wO,LenO;
bool O1;
bool Use[MAXN];
int sta[MAXN],Top;
int Nowfather,father[MAXN];
char ch[MAXN],Nowch[20];
int Cnt;
int f[MAXN];
struct Edge
{
int x,y,Next;
}e[MAXN<<1];
int elast[MAXN],tot;
void Add(int x,int y)
{
tot++;
e[tot].x=x;
e[tot].y=y;
e[tot].Next=elast[x];
elast[x]=tot;
}
int Max;
int depth[MAXN];
void dfs(int u,int fa)
{
if(f[u]==-1)
return;
depth[u]=depth[fa]+f[u];
Max=max(Max,depth[u]);
for(int i=elast[u];i;i=e[i].Next)
{
int v=e[i].y;
if(v==fa)
continue;
dfs(v,u);
}
}
void Clear()
{
Top=tot=Cnt=Nowfather=0;
wO=LenO=O1=0;
for(int i=0;i<=100;i++)
{
f[i]=elast[i]=father[i]=depth[i]=0;
}
for(int i='a';i<='z';i++)
{
Use[i]=false;
}
}
char op[30],opx[30],opy[30];
int Lenx,Leny,Numx,Numy;
void Solve()
{
Clear();
scanf("%d%s",&L,&O[1]);
LenO=strlen(O+1);
if(O[3]=='1')
{
O1=true;
}
else
{
O1=false;
for(int i=5;;i++)
{
if(O[i]==')')
break;
wO=wO*10+O[i]-48;
}
}
bool flag=false;
while(L--)
{
scanf("%s",&op[1]);
if(op[1]=='F')
{
scanf("%s",&Nowch[1]);
scanf("%s%s",&opx[1],&opy[1]);
if(flag)
continue;
if(Use[Nowch[1]])
{
flag=true;
continue;
}
Use[Nowch[1]]=true;
Cnt++;
ch[Cnt]=Nowch[1];
sta[++Top]=Cnt;
father[Cnt]=Nowfather;
Nowfather=Cnt;
Lenx=strlen(opx+1);
Leny=strlen(opy+1);
if(opx[1]=='n'||opy[1]=='n')
{
if(opx[1]=='n'&&opy[1]=='n')
{
f[Cnt]=0;
}
else
{
if(opx[1]=='n')
{
f[Cnt]=-1;
}
if(opy[1]=='n')
{
f[Cnt]=1;
}
}
}
else
{
Numx=Numy=0;
for(int i=1;i<=Lenx;i++)
{
Numx=Numx*10+opx[i]-48;
}
for(int i=1;i<=Leny;i++)
{
Numy=Numy*10+opy[i]-48;
}
if(Numx<=Numy)
{
f[Cnt]=0;
}
else
{
f[Cnt]=-1;
}
}
}
else
{
if(flag)
continue;
if(Top==0)
{
flag=true;
continue;
}
Use[ch[Nowfather]]=false;
Top--;
Nowfather=father[Nowfather];
}
}
if(flag||Top!=0)
{
puts("ERR");
return;
}
for(int i=1;i<=Cnt;i++)
{
Add(father[i],i);
}
Max=0;
dfs(0,0);
if(O1)
{
if(Max==0)
puts("Yes");
else
puts("No");
}
else
{
if(Max!=wO)
puts("No");
else
puts("Yes");
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
Solve();
}
}P3341 [ZJOI2014] 消棋子
#include <bits/stdc++.h>
using namespace std;
static char buf[1000000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
template<typename item>
inline void read(register item &x)
{
bool flag=false;
x=0;register char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
flag=true;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(flag)
x=-x;
}
const int MAXN=1e5+50;
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
struct Dot
{
int x,y,Color,a;
Dot(){}
Dot(int _x,int _y,int _Color,int _a)
{
x=_x;
y=_y;
Color=_Color;
a=_a;
}
}Son[MAXN][2];
bool operator <(Dot a,Dot b)
{
if(a.a==b.a)
{
return a.x<b.x;
}
return a.a<b.a;
}
set<Dot>Hang[MAXN],Lie[MAXN];
bool Have(int x,int y)
{
set<Dot>::iterator it=Lie[y].lower_bound(Dot(0,0,0,x));
if(it==Lie[y].end())
return false;
if((*it).x==x&&(*it).y==y)
return true;
return false;
}
Dot Find(int x,int y,int op)
{
Dot Now=Dot(-1,-1,-1,-1);
set<Dot>::iterator it;
if(op==1)
{
it=Lie[y].upper_bound(Dot(0,0,0,x));
if(it==Lie[y].begin())
return Now;
it--;
return *it;
}
if(op==2)
{
it=Lie[y].lower_bound(Dot(0,0,0,x));
if(it==Lie[y].end())
return Now;
return *it;
}
if(op==3)
{
it=Hang[x].upper_bound(Dot(0,0,0,y));
if(it==Hang[x].begin())
return Now;
it--;
return *it;
}
if(op==4)
{
it=Hang[x].lower_bound(Dot(0,0,0,y));
if(it==Hang[x].end())
return Now;
return *it;
}
return Now;
}
void Del(Dot Now)
{
Now.a=Now.x;
Lie[Now.y].erase(Now);
Now.a=Now.y;
Hang[Now.x].erase(Now);
}
bool Same(Dot a,Dot b)
{
if(a.x==b.x&&a.y==b.y)
return true;
return false;
}
bool Check(int Color)
{
int sx1=Son[Color][0].x,sy1=Son[Color][0].y,sx2=Son[Color][1].x,sy2=Son[Color][1].y;
if(sx1==sx2)
{
if(sy1+1==sy2)
return false;
if(Same(Son[Color][1],Find(sx1,sy1+1,4)))
return true;
return false;
}
if(sy1==sy2)
{
if(sx1+1==sx2)
return false;
if(Same(Son[Color][1],Find(sx1+1,sy1,2)))
return true;
return false;
}
if(sy2<sy1)
{
if(Have(sx1,sy2)==false&&Same(Find(sx1,sy2,4),Son[Color][0])&&Same(Find(sx1,sy2,2),Son[Color][1]))
return true;
if(Have(sx2,sy1)==false&&Same(Find(sx2,sy1,1),Son[Color][0])&&Same(Find(sx2,sy1,3),Son[Color][1]))
return true;
return false;
}
else
{
if(Have(sx1,sy2)==false&&Same(Find(sx1,sy2,3),Son[Color][0])&&Same(Find(sx1,sy2,2),Son[Color][1]))
return true;
if(Have(sx2,sy1)==false&&Same(Find(sx2,sy1,1),Son[Color][0])&&Same(Find(sx2,sy1,4),Son[Color][1]))
return true;
return false;
}
return false;
}
int R,C,N;
queue<int>q;
int Use[MAXN],UseColor;
bool Inq[MAXN];
int main()
{
read(R);
read(C);
read(N);
for(int i=1;i<=N;i++)
{
read(Son[i][0].x);
read(Son[i][0].y);
read(Son[i][1].x);
read(Son[i][1].y);
Son[i][0].Color=Son[i][1].Color=i;
if(Son[i][0].x>Son[i][1].x)
{
swap(Son[i][0],Son[i][1]);
}
if(Son[i][0].x==Son[i][1].x&&Son[i][0].y>Son[i][1].y)
{
swap(Son[i][0],Son[i][1]);
}
Dot Now;
for(int op=0;op<=1;op++)
{
Now=Son[i][op];
Now.a=Now.y;
Hang[Now.x].insert(Now);
Now.a=Now.x;
Lie[Now.y].insert(Now);
}
}
int Q,ans1=0;
read(Q);
while(Q--)
{
int x,y;
char op1[2],op2[2];
read(x);
read(y);
op1[0]=getchar();
while(op1[0]==' '||op1[0]=='\n')
op1[0]=getchar();
op2[0]=getchar();
while(op2[0]==' '||op2[0]=='\n')
op2[0]=getchar();
if(Have(x,y))
{
continue;
}
Dot Now1,Now2;
if(op1[0]=='U')
{
Now1=Find(x,y,1);
}
if(op1[0]=='D')
{
Now1=Find(x,y,2);
}
if(op1[0]=='L')
{
Now1=Find(x,y,3);
}
if(op1[0]=='R')
{
Now1=Find(x,y,4);
}
if(Now1.Color==-1)
continue;
if(op2[0]=='U')
{
Now2=Find(x,y,1);
}
if(op2[0]=='D')
{
Now2=Find(x,y,2);
}
if(op2[0]=='L')
{
Now2=Find(x,y,3);
}
if(op2[0]=='R')
{
Now2=Find(x,y,4);
}
if(Now2.Color==-1)
continue;
if(Now1.Color==Now2.Color)
{
Del(Now1);
Del(Now2);
ans1++;
}
}
for(int i=1;i<=R;i++)
{
Hang[i].clear();
}
for(int i=1;i<=C;i++)
{
Lie[i].clear();
}
for(int i=1;i<=N;i++)
{
Dot Now;
for(int op=0;op<=1;op++)
{
Now=Son[i][op];
Now.a=Now.y;
Hang[Now.x].insert(Now);
Now.a=Now.x;
Lie[Now.y].insert(Now);
}
}
cout<<ans1<<" ";
int ans2=0;
for(int i=1;i<=N;i++)
{
if(Check(i))
{
q.push(i);
Inq[i]=true;
}
}
while(!q.empty())
{
int Id=q.front();
q.pop();
ans2++;
Del(Son[Id][0]);
Del(Son[Id][1]);
UseColor++;
for(int op1=0;op1<=1;op1++)
{
for(int op2=1;op2<=4;op2++)
{
Dot Now=Find(Son[Id][op1].x,Son[Id][op1].y,op2);
if(Now.Color!=-1)
{
if(Inq[Now.Color]==false&&Use[Now.Color]!=UseColor)
{
Use[Now.Color]=UseColor;
if(Check(Now.Color))
{
q.push(Now.Color);
Inq[Now.Color]=true;
}
}
}
}
}
}
cout<<ans2;
}P6916 [ICPC2015 WF] Window Manager
#include <bits/stdc++.h>
using namespace std;
const int MAXN=305;
int R,C;
char op[20];
int QId;
struct Square
{
int xl,yl;
int xr,yr;
int Time;
Square(){}
Square(int _xl,int _yl,int _xr,int _yr,int _Time)
{
xl=_xl;
yl=_yl;
xr=_xr;
yr=_yr;
Time=_Time;
}
}d[MAXN];
int N;
bool cmp(Square a,Square b)
{
return a.Time<b.Time;
}
bool cmp1(Square a,Square b)
{
return a.xl<b.xl;
}
bool cmp2(Square a,Square b)
{
return a.xl>b.xl;
}
bool cmp3(Square a,Square b)
{
return a.yl<b.yl;
}
bool cmp4(Square a,Square b)
{
return a.yl>b.yl;
}
bool In(int x,int y,Square b)
{
if(x<=b.xr&&y<=b.yr&&x>=b.xl&&y>=b.yl)
return true;
return false;
}
bool Bing(int l,int r,int ll,int rr)
{
if(l>ll)
{
swap(l,ll);
swap(r,rr);
}
if(ll<=r)
return true;
return false;
}
bool Jiao(Square a,Square b)
{
if(Bing(a.xl,a.xr,b.xl,b.xr)&&Bing(a.yl,a.yr,b.yl,b.yr))
return true;
return false;
}
int Getw(Square a)
{
return a.yr-a.yl+1;
}
int Geth(Square a)
{
return a.xr-a.xl+1;
}
vector<int>NewId;
bool Del[MAXN];
int main()
{
scanf("%d%d",&C,&R);
C--;
R--;
while(scanf("%s",&op[1])!=EOF)
{
QId++;
int x,y,w,h,dx,dy;
if(op[1]=='O')
{
scanf("%d%d%d%d",&y,&x,&w,&h);
Square Now=Square(x,y,x+h-1,y+w-1,QId);
bool flag=false;
for(int i=1;i<=N;i++)
{
if(Jiao(Now,d[i]))
{
flag=true;
break;
}
}
if(Now.xr>R||Now.yr>C)
flag=true;
if(flag)
{
printf("Command %d: OPEN - window does not fit\n",QId);
}
else
{
d[++N]=Now;
}
}
if(op[1]=='C')
{
scanf("%d%d",&y,&x);
bool flag=false;
for(int i=1;i<=N;i++)
{
if(In(x,y,d[i]))
{
flag=true;
N--;
for(int j=i;j<=N;j++)
{
d[j]=d[j+1];
}
break;
}
}
if(flag==false)
{
printf("Command %d: CLOSE - no window at given position\n",QId);
}
}
if(op[1]=='R')
{
scanf("%d%d%d%d",&y,&x,&w,&h);
bool flag=false;
for(int i=1;i<=N;i++)
{
if(In(x,y,d[i]))
{
flag=true;
Square Now=d[i];
Now.xr=Now.xl+h-1;
Now.yr=Now.yl+w-1;
bool flag2=false;
for(int j=1;j<=N;j++)
{
if(i==j)
continue;
if(Jiao(Now,d[j]))
{
flag2=true;
break;
}
}
if(Now.xr>R||Now.yr>C)
flag2=true;
if(flag2==false)
{
d[i]=Now;
break;
}
else
{
printf("Command %d: RESIZE - window does not fit\n",QId);
}
break;
}
}
if(flag==false)
{
printf("Command %d: RESIZE - no window at given position\n",QId);
}
}
if(op[1]=='M')
{
scanf("%d%d%d%d",&y,&x,&dy,&dx);
if(dx==0&&dy==0)
continue;
bool flag=false;
if(dy==0)
{
if(dx>0)
{
for(int i=1;i<=QId;i++)
Del[i]=false;
NewId.clear();
for(int i=1;i<=N;i++)
{
if(In(x,y,d[i]))
{
flag=true;
NewId.push_back(i);
Del[i]=true;
break;
}
}
if(flag==false)
{
printf("Command %d: MOVE - no window at given position\n",QId);
continue;
}
int Sum=dx;
while(true)
{
bool Full=false;
for(int i=0;i<NewId.size();i++)
{
if(d[NewId[i]].xr==R)
{
Full=true;
break;
}
}
if(Full)
break;
int MinId=-1,Min=1e9+1;
for(int i=0;i<NewId.size();i++)
{
Square Now=d[NewId[i]];
for(int j=1;j<=N;j++)
{
if(Del[j])
continue;
if(Bing(Now.yl,Now.yr,d[j].yl,d[j].yr)==false)
continue;
if(Now.xr>d[j].xl)
continue;
if(Min>d[j].xl-Now.xr-1)
{
Min=d[j].xl-Now.xr-1;
MinId=j;
}
}
}
for(int i=0;i<NewId.size();i++)
{
if(Min>=R-d[NewId[i]].xr)
{
Min=R-d[NewId[i]].xr;
MinId=-1;
}
}
if(MinId==-1||Min>Sum)
{
if(Min>=Sum)
{
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].xl+=Sum;
d[NewId[i]].xr+=Sum;
}
Sum=0;
}
else
{
Sum-=Min;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].xl+=Min;
d[NewId[i]].xr+=Min;
}
}
break;
}
else
{
Sum-=Min;
Del[MinId]=true;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].xl+=Min;
d[NewId[i]].xr+=Min;
}
NewId.push_back(MinId);
}
}
if(Sum>0)
{
printf("Command %d: MOVE - moved %d instead of %d\n",QId,dx-Sum,dx);
}
}
else
{
dx=-dx;
for(int i=1;i<=QId;i++)
Del[i]=false;
NewId.clear();
for(int i=1;i<=N;i++)
{
if(In(x,y,d[i]))
{
flag=true;
NewId.push_back(i);
Del[i]=true;
break;
}
}
if(flag==false)
{
printf("Command %d: MOVE - no window at given position\n",QId);
continue;
}
int Sum=dx;
while(true)
{
bool Full=false;
for(int i=0;i<NewId.size();i++)
{
if(d[NewId[i]].xl==0)
{
Full=true;
break;
}
}
if(Full)
break;
int MinId=-1,Min=1e9+1;
for(int i=0;i<NewId.size();i++)
{
Square Now=d[NewId[i]];
for(int j=1;j<=N;j++)
{
if(Del[j])
continue;
if(Now.xl<d[j].xr)
continue;
if(Bing(Now.yl,Now.yr,d[j].yl,d[j].yr)==false)
continue;
if(Min>Now.xl-d[j].xr-1)
{
Min=Now.xl-d[j].xr-1;
MinId=j;
}
}
}
for(int i=0;i<NewId.size();i++)
{
if(Min>=d[NewId[i]].xl)
{
Min=d[NewId[i]].xl;
MinId=-1;
}
}
if(MinId==-1||Min>=Sum)
{
if(Min>=Sum)
{
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].xl-=Sum;
d[NewId[i]].xr-=Sum;
}
Sum=0;
}
else
{
Sum-=Min;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].xl-=Min;
d[NewId[i]].xr-=Min;
}
}
break;
}
else
{
Sum-=Min;
Del[MinId]=true;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].xl-=Min;
d[NewId[i]].xr-=Min;
}
NewId.push_back(MinId);
}
}
if(Sum>0)
{
printf("Command %d: MOVE - moved %d instead of %d\n",QId,dx-Sum,dx);
}
}
}
else
{
if(dy>0)
{
for(int i=1;i<=QId;i++)
Del[i]=false;
NewId.clear();
for(int i=1;i<=N;i++)
{
if(In(x,y,d[i]))
{
flag=true;
NewId.push_back(i);
Del[i]=true;
break;
}
}
if(flag==false)
{
printf("Command %d: MOVE - no window at given position\n",QId);
continue;
}
int Sum=dy;
while(true)
{
bool Full=false;
for(int i=0;i<NewId.size();i++)
{
if(d[NewId[i]].yr==C)
{
Full=true;
break;
}
}
if(Full)
break;
int MinId=-1,Min=1e9+1;
for(int i=0;i<NewId.size();i++)
{
Square Now=d[NewId[i]];
for(int j=1;j<=N;j++)
{
if(Del[j])
continue;
if(Bing(Now.xl,Now.xr,d[j].xl,d[j].xr)==false)
continue;
if(Now.yr>d[j].yl)
continue;
if(Min>d[j].yl-Now.yr-1)
{
Min=d[j].yl-Now.yr-1;
MinId=j;
}
}
}
for(int i=0;i<NewId.size();i++)
{
if(C-d[NewId[i]].yr<=Min)
{
Min=C-d[NewId[i]].yr;
MinId=-1;
}
}
if(MinId==-1||Min>=Sum)
{
if(Min>=Sum)
{
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].yl+=Sum;
d[NewId[i]].yr+=Sum;
}
Sum=0;
}
else
{
Sum-=Min;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].yl+=Min;
d[NewId[i]].yr+=Min;
}
}
break;
}
else
{
Sum-=Min;
Del[MinId]=true;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].yl+=Min;
d[NewId[i]].yr+=Min;
}
NewId.push_back(MinId);
}
}
if(Sum>0)
{
printf("Command %d: MOVE - moved %d instead of %d\n",QId,dy-Sum,dy);
}
}
else
{
dy=-dy;
for(int i=1;i<=QId;i++)
Del[i]=false;
NewId.clear();
for(int i=1;i<=N;i++)
{
if(In(x,y,d[i]))
{
flag=true;
NewId.push_back(i);
Del[i]=true;
break;
}
}
if(flag==false)
{
printf("Command %d: MOVE - no window at given position\n",QId);
continue;
}
int Sum=dy;
while(true)
{
bool Full=false;
for(int i=0;i<NewId.size();i++)
{
if(d[NewId[i]].yl==0)
{
Full=true;
break;
}
}
if(Full)
break;
int MinId=-1,Min=1e9+1;
for(int i=0;i<NewId.size();i++)
{
Square Now=d[NewId[i]];
for(int j=1;j<=N;j++)
{
if(Del[j])
continue;
if(Bing(Now.xl,Now.xr,d[j].xl,d[j].xr)==false)
continue;
if(Now.yl<d[j].yr)
continue;
if(Min>Now.yl-d[j].yr-1)
{
Min=Now.yl-d[j].yr-1;
MinId=j;
}
}
}
for(int i=0;i<NewId.size();i++)
{
if(Min>=d[NewId[i]].yl)
{
Min=d[NewId[i]].yl;
MinId=-1;
}
}
if(MinId==-1||Min>=Sum)
{
if(Min>=Sum)
{
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].yl-=Sum;
d[NewId[i]].yr-=Sum;
}
Sum=0;
}
else
{
Sum-=Min;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].yl-=Min;
d[NewId[i]].yr-=Min;
}
}
break;
}
else
{
Sum-=Min;
Del[MinId]=true;
for(int i=0;i<NewId.size();i++)
{
d[NewId[i]].yl-=Min;
d[NewId[i]].yr-=Min;
}
NewId.push_back(MinId);
}
}
if(Sum>0)
{
printf("Command %d: MOVE - moved %d instead of %d\n",QId,dy-Sum,dy);
}
}
}
}
}
sort(d+1,d+N+1,cmp);
printf("%d window(s):\n",N);
for(int i=1;i<=N;i++)
{
printf("%d %d %d %d\n",d[i].yl,d[i].xl,Getw(d[i]),Geth(d[i]));
}
}P7963 [NOIP2021] 棋局
#include<iostream>
#include <algorithm>
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x)
{
bool flag=false;
x=0;register char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
flag=true;
c=getchar();
}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(flag)
x=-x;
}
static char cc[10000];
template<typename item>
inline void print(register item x)
{
if(x==0)
{
cc[0]='0';
putchar(cc[0]);
return;
}
if(x<0)
{
cc[0]='-';
putchar(cc[0]);
x=-x;
}
register long long len=0;
while(x)cc[len++]=x%10+'0',x/=10;
while(len--)putchar(cc[len]);
}
const int MAXN=2e6+50;
void InOut(int op)
{
freopen("chess.in","r",stdin);
if(op)
freopen("chess.out","w",stdout);
}
int N,M,Q;
bool Can(int x,int y)
{
if(x<1||y<1||x>N||y>M)
return false;
return true;
}
int ALL;
int Edge[4][MAXN<<1];
int Ans[MAXN];
struct Node
{
int Color,Level,x,y,Id;
}Piece[MAXN];
bool CanEat(Node a,Node b)
{
if(a.Color!=b.Color&&a.Level>=b.Level)
return true;
return false;
}
bool cmp1(Node a,Node b)
{
if(a.Level==b.Level)
return a.Id<b.Id;
return a.Level<b.Level;
}
bool cmp2(Node a,Node b)
{
return a.Id<b.Id;
}
void LSHLevel()
{
std::sort(Piece+1,Piece+Q+1,cmp1);
for(int i=1;i<=Q;i++)
{
Piece[i].Level=i;
}
std::sort(Piece+1,Piece+Q+1,cmp2);
}
int HaveNode[MAXN];
int GetId(int op,int x,int y)
{
if(op==0)
return (x-1)*M+y;
else
return (y-1)*N+x;
}
int GetX(int Id)
{
return (Id-1)/M+1;
}
int GetY(int Id)
{
return (Id-1)%M+1;
}
int max(int a,int b)
{
return a>b?a:b;
}
struct SegmentTree
{
int Root[MAXN];
int ls[MAXN<<2],rs[MAXN<<2],Size[MAXN<<2];
int CntId;
void Init()
{
for(int i=1;i<=ALL;i++)
Root[i]=0;
for(int i=1;i<=CntId;i++)
{
ls[i]=rs[i]=Size[i]=0;
}
CntId=0;
}
int Merge(int u1,int u2,int l,int r)
{
if(u1&&u2)
{
if(u1==u2)
return u1;
}
if(!u1||!u2)
{
return u1+u2;
}
if(l==r)
{
Size[u1]=max(Size[u1],Size[u2]);
return u1;
}
int Mid=l+r>>1;
ls[u1]=Merge(ls[u1],ls[u2],l,Mid);
rs[u1]=Merge(rs[u1],rs[u2],Mid+1,r);
Size[u1]=Size[ls[u1]]+Size[rs[u1]];
return u1;
}
void Insert(int &u,int l,int r,int x)
{
if(u==0)
{
u=++CntId;
}
if(l==r)
{
Size[u]=1;
return;
}
int Mid=l+r>>1;
if(x<=Mid)
Insert(ls[u],l,Mid,x);
else
Insert(rs[u],Mid+1,r,x);
Size[u]=Size[ls[u]]+Size[rs[u]];
}
void Delete(int &u,int l,int r,int x)
{
if(u==0)
{
return;
}
if(l==r)
{
Size[u]=0;
return;
}
int Mid=l+r>>1;
if(x<=Mid)
Delete(ls[u],l,Mid,x);
else
Delete(rs[u],Mid+1,r,x);
Size[u]=Size[ls[u]]+Size[rs[u]];
}
int Query(int u,int l,int r,int x,int y)
{
if(!u)
return 0;
if(x<=l&&r<=y)
{
return Size[u];
}
int Mid=l+r>>1,Sum=0;
if(x<=Mid&&y>=l)
Sum+=Query(ls[u],l,Mid,x,y);
if(x<=r&&y>=Mid+1)
Sum+=Query(rs[u],Mid+1,r,x,y);
return Sum;
}
bool Query(int u,int l,int r,int x)
{
if(u==0)
{
return false;
}
if(l==r)
{
if(Size[u])
return true;
else
return false;
}
int Mid=l+r>>1;
if(x<=Mid)
return Query(ls[u],l,Mid,x);
else
return Query(rs[u],Mid+1,r,x);
}
}trId[2],trLevel[2];
void Insert1(int x,int y,int z)
{
trId[0].Insert(trId[0].Root[z],1,ALL,GetId(0,x,y));
trId[1].Insert(trId[1].Root[z],1,ALL,GetId(1,x,y));
}
void Insert2(int Nodeid,int z)
{
trLevel[Piece[Nodeid].Color].Insert(trLevel[0].Root[z],1,ALL,Piece[Nodeid].Level);
}
struct BingChaJi
{
int father[MAXN],Min[MAXN],Max[MAXN];
void Init()
{
for(int i=1;i<=ALL;i++)
{
father[i]=i;
Min[i]=1e9;Max[i]=0;
}
}
int getfather(int x)
{
if(x!=father[x])
father[x]=getfather(father[x]);
return father[x];
}
void Merge(int x,int y)
{
int fx=getfather(x),fy=getfather(y);
if(fx==fy)
return;
father[fy]=fx;
}
}Set[3];
void Init()
{
for(int i=1;i<=ALL;i++)
{
Edge[0][i]=Edge[1][i]=Edge[2][i]=Edge[3][i]=Ans[i]=HaveNode[i]=0;
}
trId[0].Init();
trId[1].Init();
trLevel[0].Init();
trLevel[1].Init();
Set[0].Init();
Set[1].Init();
Set[2].Init();
}
char opt[MAXN];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
bool vis[MAXN];
int Mergedfs(int op,int x,int y,int fa)
{
if(op==4)
{
vis[GetId(0,x,y)]=true;
if(HaveNode[GetId(0,x,y+1)]==0&&Can(x,y+1)&&Edge[3][GetId(0,x,y)]==2)
{
Set[1].Merge(Set[1].getfather(GetId(0,x,fa)),Set[1].getfather(GetId(0,x,y+1)));
return Mergedfs(op,x,y+1,fa);
}
else
{
return y;
}
}
if(op==2)
{
vis[GetId(0,x,y)]=true;
if(HaveNode[GetId(0,x+1,y)]==0&&Can(x+1,y)&&Edge[1][GetId(0,x,y)]==2)
{
Set[2].Merge(Set[2].getfather(GetId(0,fa,y)),Set[2].getfather(GetId(0,x+1,y)));
return Mergedfs(op,x+1,y,fa);
}
else
{
return x;
}
}
}
void dfs3(int x,int y,int fx,int fy)
{
vis[GetId(0,x,y)]=true;
trId[0].Insert(trId[0].Root[GetId(0,fx,fy)],1,ALL,GetId(0,x,y));
trId[1].Insert(trId[1].Root[GetId(0,fx,fy)],1,ALL,GetId(1,x,y));
for(int i=0;i<4;i++)
{
if(Edge[i][GetId(0,x,y)]==3&&vis[GetId(0,x+dx[i+1],y+dy[i+1])]==false)
{
if(HaveNode[GetId(0,x+dx[i+1],y+dy[i+1])]==0)
{
Set[0].Merge(Set[0].getfather(GetId(0,fx,fy)),Set[0].getfather(GetId(0,x+dx[i+1],y+dy[i+1])));
dfs3(x+dx[i+1],y+dy[i+1],fx,fy);
}
else
{
int t=HaveNode[GetId(0,x+dx[i+1],y+dy[i+1])];
trLevel[Piece[t].Color].Insert(trLevel[Piece[t].Color].Root[GetId(0,fx,fy)],1,Q,Piece[t].Level);
}
}
}
}
void Read()
{
read(N);
read(M);
read(Q);
ALL=N*M;
Init();
for(int i=1;i<=N;i++)
{
for(int j=1;j<M;j++)
{
opt[j]=getchar();
while(opt[j]<'0'||opt[j]>'9')
opt[j]=getchar();
Edge[3][GetId(0,i,j)]=Edge[2][GetId(0,i,j+1)]=opt[j]-'0';
}
}
for(int i=1;i<N;i++)
{
for(int j=1;j<=M;j++)
{
opt[j]=getchar();
while(opt[j]<'0'||opt[j]>'9')
opt[j]=getchar();
Edge[0][GetId(0,i+1,j)]=Edge[1][GetId(0,i,j)]=opt[j]-'0';
}
}
for(int i=1;i<=Q;i++)
{
read(Piece[i].Color);
read(Piece[i].Level);
read(Piece[i].x);
read(Piece[i].y);
Piece[i].Id=i;
HaveNode[GetId(0,Piece[i].x,Piece[i].y)]=i;
}
}
int SolveEdge1(Node Now)
{
int ans=0;
int fx=Set[0].getfather(GetId(0,Now.x,Now.y));
for(int i=0;i<4;i++)
{
if(Edge[i][GetId(0,Now.x,Now.y)]==1)
{
if(HaveNode[GetId(0,Now.x+dx[i+1],Now.y+dy[i+1])]==0)
{
if(trId[0].Query(trId[0].Root[fx],1,ALL,GetId(0,Now.x+dx[i+1],Now.y+dy[i+1]))==false
{
ans++;
}
}
else
{
if(CanEat(Now,Piece[HaveNode[GetId(0,Now.x+dx[i+1],Now.y+dy[i+1])]]))
{
int NowColor=Piece[HaveNode[GetId(0,Now.x+dx[i+1],Now.y+dy[i+1])]].Color,NowLevel=Piece[HaveNode[GetId(0,Now.x+dx[i+1],Now.y+dy[i+1])]].Level;
if(trLevel[NowColor].Query(trLevel[NowColor].Root[fx],1,Q,NowLevel)==false)
{
ans++;
}
}
}
}
}
return ans;
}
#include <vector>
std::vector<int>Eatid;
int SolveEdge2(Node Now)
{
int ans=0;
int l1,r1,l2,r2;
l1=Set[1].Min[Set[1].getfather(GetId(0,Now.x,Now.y))];
r1=Set[1].Max[Set[1].getfather(GetId(0,Now.x,Now.y))];
l2=Set[2].Min[Set[2].getfather(GetId(0,Now.x,Now.y))];
r2=Set[2].Max[Set[2].getfather(GetId(0,Now.x,Now.y))];
int fx=Set[0].getfather(GetId(0,Now.x,Now.y));
ans+=r1-l1+1-trId[0].Query(trId[0].Root[fx],1,ALL,GetId(0,Now.x,l1),GetId(0,Now.x,r1));
ans+=r2-l2+1-trId[1].Query(trId[1].Root[fx],1,ALL,GetId(1,l2,Now.y),GetId(1,r2,Now.y));
Eatid.clear();
if(Edge[2][GetId(0,Now.x,l1)]==2)
Eatid.push_back(GetId(0,Now.x,l1-1));
if(Edge[3][GetId(0,Now.x,r1)]==2)
Eatid.push_back(GetId(0,Now.x,r1+1));
if(Edge[0][GetId(0,l2,Now.y)]==2)
Eatid.push_back(GetId(0,l2-1,Now.y));
if(Edge[1][GetId(0,r2,Now.y)]==2)
Eatid.push_back(GetId(0,r2+1,Now.y));
for(int i=0;i<Eatid.size();i++)
{
if(CanEat(Now,Piece[HaveNode[Eatid[i]]]))
{
int NowColor=Piece[HaveNode[Eatid[i]]].Color,NowLevel=Piece[HaveNode[Eatid[i]]].Level;
if(trLevel[NowColor].Query(trLevel[NowColor].Root[fx],1,Q,NowLevel)==false)
{
ans++;
}
}
}
return ans;
}
int SolveEdge3(Node Now)
{
int ans=0;
int fx=Set[0].getfather(GetId(0,Now.x,Now.y));
ans+=trId[0].Size[trId[0].Root[fx]]-trId[0].Query(trId[0].Root[fx],1,ALL,GetId(0,Now.x,Now.y));
ans+=trLevel[Now.Color^1].Query(trLevel[Now.Color^1].Root[fx],1,Q,1,Now.Level-1);
return ans;
}
std::vector<int>E2,E3;
int min(int x,int y)
{
return x<y?x:y;
}
void Del(Node Now)
{
HaveNode[GetId(0,Now.x,Now.y)]=0;
E3.clear();
for(int i=0;i<4;i++)
{
if(Edge[i][GetId(0,Now.x,Now.y)]==3)
{
E3.push_back(GetId(0,Now.x+dx[i+1],Now.y+dy[i+1]));
}
}
int ffx=Set[0].getfather(GetId(0,Now.x,Now.y));
trId[0].Insert(trId[0].Root[ffx],1,ALL,GetId(0,Now.x,Now.y));
trId[1].Insert(trId[1].Root[ffx],1,ALL,GetId(1,Now.x,Now.y));
for(int i=0;i<E3.size();i++)
{
int fx=Set[0].getfather(GetId(0,Now.x,Now.y)),fy=Set[0].getfather(E3[i]);
if(HaveNode[E3[i]])
{
int NowColor=Piece[HaveNode[E3[i]]].Color,NowLevel=Piece[HaveNode[E3[i]]].Level;
trLevel[NowColor].Insert(trLevel[NowColor].Root[fx],1,Q,NowLevel);
continue;
}
if(trId[0].Size[trId[0].Root[fy]])
trId[0].Root[fx]=trId[0].Merge(trId[0].Root[fx],trId[0].Root[fy],1,ALL);
if(trId[1].Size[trId[1].Root[fy]])
trId[1].Root[fx]=trId[1].Merge(trId[1].Root[fx],trId[1].Root[fy],1,ALL);
if(trLevel[0].Size[trLevel[0].Root[fy]])
trLevel[0].Root[fx]=trLevel[0].Merge(trLevel[0].Root[fx],trLevel[0].Root[fy],1,Q);
if(trLevel[1].Size[trLevel[1].Root[fy]])
trLevel[1].Root[fx]=trLevel[1].Merge(trLevel[1].Root[fx],trLevel[1].Root[fy],1,Q);
Set[0].Merge(fx,fy);
}
trLevel[Now.Color].Delete(trLevel[Now.Color].Root[ffx],1,Q,Now.Level);
if(Edge[0][GetId(0,Now.x,Now.y)]==Edge[1][GetId(0,Now.x,Now.y)]&&Edge[0][GetId(0,Now.x,Now.y)]==2&&HaveNode[GetId(0,Now.x-1,Now.y)]==0&&HaveNode[GetId(0,Now.x+1,Now.y)]==0)
{
int fx=Set[2].getfather(GetId(0,Now.x-1,Now.y)),fy=Set[2].getfather(GetId(0,Now.x+1,Now.y));
Set[2].Max[fx]=Set[2].Max[fy];
Set[2].Merge(fx,fy);
Set[2].Merge(Set[2].getfather(GetId(0,Now.x-1,Now.y)),Set[2].getfather(GetId(0,Now.x,Now.y)));
}
else
{
if(Edge[0][GetId(0,Now.x,Now.y)]==2&&HaveNode[GetId(0,Now.x-1,Now.y)]==0)
{
Set[2].Merge(Set[2].getfather(GetId(0,Now.x-1,Now.y)),Set[2].getfather(GetId(0,Now.x,Now.y)));
Set[2].Max[Set[2].getfather(GetId(0,Now.x-1,Now.y))]=Now.x;
}
else
{
if(Edge[1][GetId(0,Now.x,Now.y)]==2&&HaveNode[GetId(0,Now.x+1,Now.y)]==0)
{
Set[2].Merge(Set[2].getfather(GetId(0,Now.x+1,Now.y)),Set[2].getfather(GetId(0,Now.x,Now.y)));
Set[2].Min[Set[2].getfather(GetId(0,Now.x+1,Now.y))]=Now.x;
}
else
{
Set[2].Min[GetId(0,Now.x,Now.y)]=Set[2].Max[GetId(0,Now.x,Now.y)]=Now.x;
}
}
}
if(Edge[2][GetId(0,Now.x,Now.y)]==Edge[3][GetId(0,Now.x,Now.y)]&&Edge[2][GetId(0,Now.x,Now.y)]==2&&HaveNode[GetId(0,Now.x,Now.y-1)]==0&&HaveNode[GetId(0,Now.x,Now.y+1)]==0)
{
int fx=Set[1].getfather(GetId(0,Now.x,Now.y-1)),fy=Set[1].getfather(GetId(0,Now.x,Now.y+1));
Set[1].Max[fx]=Set[1].Max[fy];
Set[1].Merge(fx,fy);
Set[1].Merge(Set[1].getfather(GetId(0,Now.x,Now.y-1)),Set[1].getfather(GetId(0,Now.x,Now.y)));
}
else
{
if(Edge[2][GetId(0,Now.x,Now.y)]==2&&HaveNode[GetId(0,Now.x,Now.y-1)]==0)
{
Set[1].Merge(Set[1].getfather(GetId(0,Now.x,Now.y-1)),Set[1].getfather(GetId(0,Now.x,Now.y)));
Set[1].Max[Set[1].getfather(GetId(0,Now.x,Now.y-1))]=Now.y;
}
else
{
if(Edge[3][GetId(0,Now.x,Now.y)]==2&&HaveNode[GetId(0,Now.x,Now.y+1)]==0)
{
Set[1].Merge(Set[1].getfather(GetId(0,Now.x,Now.y+1)),Set[1].getfather(GetId(0,Now.x,Now.y)));
Set[1].Min[Set[1].getfather(GetId(0,Now.x,Now.y+1))]=Now.y;
}
else
{
Set[1].Min[GetId(0,Now.x,Now.y)]=Set[1].Max[GetId(0,Now.x,Now.y)]=Now.y;
}
}
}
}
void Solve()
{
Read();
LSHLevel();
for(int i=1;i<=ALL;i++)
vis[i]=false;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
if(HaveNode[GetId(0,i,j)]==0&&vis[GetId(0,i,j)]==0)
{
Set[1].Min[GetId(0,i,j)]=j;
Set[1].Max[GetId(0,i,j)]=Mergedfs(4,i,j,j);
}
}
}
for(int i=1;i<=ALL;i++)
vis[i]=false;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
if(HaveNode[GetId(0,i,j)]==0&&vis[GetId(0,i,j)]==0)
{
Set[2].Min[GetId(0,i,j)]=i;
Set[2].Max[GetId(0,i,j)]=Mergedfs(2,i,j,i);
}
}
}
for(int i=1;i<=ALL;i++)
vis[i]=false;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
if(vis[GetId(0,i,j)]==0&&HaveNode[GetId(0,i,j)]==0)
{
dfs3(i,j,i,j);
}
}
}
for(int i=Q;i>=1;i--)
{
Del(Piece[i]);
Ans[i]=SolveEdge1(Piece[i])+
SolveEdge2(Piece[i])+
SolveEdge3(Piece[i]);
}
for(int i=1;i<=Q;i++)
{
print(Ans[i]);
putchar('\n');
}
}
int main()
{
int T;
read(T);
while(T--)
{
Solve();
}
fwrite(obuf,p3-obuf,1,stdout);
} 未完待续。