模拟[懒得编号]考试总结

T2.寻宝

先用bfs把联通块缩起来，然后对100个门跑传递闭包，没门的不用管
一个询问如果在一块里直接可达，不在一块里如果可达就有解

#include 
using namespace std;
#define int long long 
#define pb push_back
#define pir pair
#define mp make_pair
const int N=50005;
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
vector a[N],p[N];
char s[N];int n,m,k,qq,tot,cnt;
queue  q;map  mmp;
inline void bfs(int px,int py,int id)
{
	q.push(mp(px,py));p[px][py]=id;
	while(q.size())
	{	
		int x=q.front().first,y=q.front().second;q.pop();
		if(x>1&&a[x-1][y]==1&&p[x-1][y]==0)p[x-1][y]=id,q.push(mp(x-1,y));
		if(y>1&&a[x][y-1]==1&&p[x][y-1]==0)p[x][y-1]=id,q.push(mp(x,y-1));
		if(x>n>>m>>k>>qq;
	for(int i=0;i<=m+1;i++)a[0].pb(0),p[0].pb(0);
	for(int i=1;i<=n;i++)
	{
		a[i].pb(0);p[i].pb(0);scanf("%s",s+1);
		for(int j=1;j<=m;j++)
		{
			if(s[j]=='#')a[i].pb(0);
			else a[i].pb(1);
			p[i].pb(0);
		}
		a[i].pb(0);p[i].pb(0);
	}
	for(int i=0;i<=m+1;i++)a[n+1].pb(0),p[n+1].pb(0);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
		if(p[i][j]==0&&a[i][j]==1)bfs(i,j,++tot);
	for(int i=1;i<=k;i++)
	{
		int x=read(),y=read(),xx=read(),yy=read();
		int id1=p[x][y],id2=p[xx][yy],p1,p2;
		if(mmp.find(id1)==mmp.end())mmp[id1]=++cnt,p1=cnt,b[p1][p1]=1;
		else p1=mmp[id1];
		if(mmp.find(id2)==mmp.end())mmp[id2]=++cnt,p2=cnt,b[p2][p2]=1;
		else p2=mmp[id2];
		b[p1][p2]=1;
	}
	for(int kk=1;kk<=cnt;kk++)for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++)
	 b[i][j]=b[i][j]|(b[i][kk]&b[kk][j]);
	for(int i=1;i<=qq;i++)
	{
		int x=read(),y=read(),xx=read(),yy=read();
		int id1=p[x][y],id2=p[xx][yy];
		assert(id1&&id2);
		if(id1==id2){puts("1");continue;}
		if(mmp.find(id1)==mmp.end()||mmp.find(id2)==mmp.end()){puts("0");continue;}
		int p1=mmp[id1],p2=mmp[id2];
		if(b[p1][p2])puts("1");else puts("0");
	}
	return 0;
}

T3.序列

被称李超树模板题，于是滚去学了李超树
左右贡献相互独立，可以把柿子拆开，两个问题同理，以右端点为例
设\(sa_i=\sum_{j=1}^i a_j\)，\(sb_i=\sum_{j=1}^ib_j\)
最优即\(\max_{1\leq l\leq r}\{(sa_{r}-sa_{l-1})-k(sb_{r}-sb_{l-1})\}\)
即\(sa_r-k\cdot sb_{r}+\max_{0\leq l，离线之后李超树维护直线即可

#include 
using namespace std;
#define int long long
const int N=1000050;
int n,m,ans[N],pa[N],pb[N],suma[N],sumb[N];
struct line{int k,b;}a[N];
struct node{int id,k;};vector  p[N];
struct tree{
	int l,r,ma;
}tr[8*N];
inline int get(int id,int x){return a[id].k*x+a[id].b;}
inline double gett(int id1,int id2){return (1.0*a[id2].b-a[id1].b)/(1.0*a[id1].k-a[id2].k);}
void build(int id,int l,int r)
{
	tr[id].l=l;tr[id].r=r;tr[id].ma=0;
	if(l==r)return;int mid=(l+r)>>1;
	build(id*2,l,mid);build(id*2+1,mid+1,r);
}
void add(int id,int v)
{	
	int mid=(tr[id].l+tr[id].r)>>1;
	if(!tr[id].ma){tr[id].ma=v;return;}
	int p1=get(tr[id].ma,tr[id].l),p2=get(tr[id].ma,tr[id].r),
		 p3=get(v,tr[id].l),p4=get(v,tr[id].r);
	if(p3<=p1&&p4<=p2)return;
	if(p3>=p1&&p4>=p2){tr[id].ma=v;return;}
	double p=gett(tr[id].ma,v);
	if(p3>=p1)
	{	
		if(p<=mid)add(id*2,v);
		else add(id*2+1,tr[id].ma),tr[id].ma=v;
	}
	else
	{	
		if(p<=mid)add(id*2,tr[id].ma),tr[id].ma=v;
		else add(id*2+1,v);
	}
}
inline int clac(int x,int p1,int p2){if(p1>p2)swap(p1,p2);return (get(p1,x)>=get(p2,x))?p1:p2;}
int getans(int id,int p)
{	
	if(tr[id].l==tr[id].r)return tr[id].ma;
	int mid=(tr[id].l+tr[id].r)>>1;
	if(p<=mid)return clac(p,tr[id].ma,getans(id*2,p));
	else return clac(p,tr[id].ma,getans(id*2+1,p));
}
signed main()	
{
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	cin>>n>>m;build(1,-1e6,1e6);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&pa[i],&pb[i]);
	for(int i=1;i<=m;i++)
	{	
		int pp,k;scanf("%lld%lld",&pp,&k);
		p[pp].push_back((node){i,k});
	}
	for(int i=1;i<=n;i++)suma[i]=pa[i]+suma[i-1],sumb[i]=sumb[i-1]+pb[i];
	for(int i=1;i<=n;i++)
	{	
		for(int j=0;j=1;i--)suma[i]=suma[i+1]+pa[i],sumb[i]=sumb[i+1]+pb[i];
	build(1,-1e6,1e6);
	for(int i=n;i>=1;i--)
	{
		for(int j=0;j