模拟赛1

模拟赛2

模拟赛3

模拟赛4

模拟赛5

模拟赛6

模拟赛7

模拟赛8

模拟赛9

T1 三角田地

给你一些点，问他们能够组成的直角三角形的面积的和。对1e9+7取模
\(N \le 10^5, -10^4 \le X_i,Y_i\le 10^4\)
好好好赛时没取模，爆炸！
做法大概就是把同行的丢树状数组里，算一下贡献，再把同列的丢树状数组里，算一下贡献

#include<bits/stdc++.h>
#include<cstdio>
#define fir first
#define se second
#define MOD 1000000007
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long ll;
typedef pair<pair<ll,ll>,ll> PIII;
const int N=1e5+50;
PIII a[N];
ll c1[N],c2[N];
bool cmp2(const PIII &a,const PIII &b){
	return a.fir.se<b.fir.se;
}
void add(ll c[],ll x,ll i){
	if(!i)return;
	while(i<=20010){
		(c[i]+=x)%=MOD; 
		i+=lowbit(i);
	}
}
ll query(ll c[],ll i){
	if(!i)return 0;
	ll ans=0;
	while(i){
		(ans+=c[i])%=MOD;
		i-=lowbit(i);
	}
	return ans;
}
int main(){
//	freopen("triangles.in","r",stdin);
//	freopen("triangles.out","w",stdout);
	int n;ll ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].fir.fir,&a[i].fir.se);
		a[i].fir.fir+=10001;a[i].fir.se+=10001;
	} 
	sort(a+1,a+n+1); 
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		while(r<n&&a[r+1].fir.fir==a[l].fir.fir)r++;
		for(int i=l;i<=r;i++){
			add(c1,a[i].fir.se,a[i].fir.se);
			add(c2,1,a[i].fir.se);
		}
		for(int i=l;i<=r;i++){
			(a[i].se+=1ll*query(c2,a[i].fir.se)*a[i].fir.se-query(c1,a[i].fir.se)%MOD)%=MOD;
			(a[i].se+=1ll*(query(c1,20001)-query(c1,a[i].fir.se))-(query(c2,20001)-query(c2,a[i].fir.se))*a[i].fir.se%MOD)%=MOD;
		}
		for(int i=l;i<=r;i++){
			add(c1,-a[i].fir.se,a[i].fir.se);
			add(c2,-1,a[i].fir.se);
		}
		i=r;
	}
	sort(a+1,a+n+1,cmp2); 
	for(int i=1;i<=n;i++){
		int l=i,r=i;
		while(r<n&&a[r+1].fir.se==a[l].fir.se)r++;
		for(int i=l;i<=r;i++){
			add(c1,a[i].fir.fir,a[i].fir.fir);
			add(c2,1,a[i].fir.fir);
		}
		for(int i=l;i<=r;i++){
			(ans+=(1ll*query(c2,a[i].fir.fir)*a[i].fir.fir-query(c1,a[i].fir.fir))*a[i].se)%=MOD;
			(ans+=(1ll*(query(c1,20001)-query(c1,a[i].fir.fir))-(query(c2,20001)-query(c2,a[i].fir.fir))*a[i].fir.fir)*a[i].se)%=MOD;
		}
		for(int i=l;i<=r;i++){
			add(c1,-a[i].fir.fir,a[i].fir.fir);
			add(c2,-1,a[i].fir.fir);
		}
		i=r;
	}
	printf("%lld",(ans+MOD)%MOD);
	return 0;
}

T4

有N个城市，被M条双向道路连接。 在保证图联通的情况下去掉尽可能多的边使得剩余边边权和最小。

问对于每一条边，可能被保留时边权最大为多少

\(N\le 10^5,N-1 \le M \le 10^6 ,0\le w_i\le 10^9\)

有N个城市，被M条双向道路连接。 每条双向道路都有一个维修费用。
国王想要去掉尽可能多的边，使得留下来的边依旧能使王国的任意两个城市之间都有经过一条或多条边的路径。在所有的方案中， 国王希望留下来的边的维修费用之和最小。
现在，国王准备调整一些边的维修费用来影响最后留下的边的结果。对于每条边，他希望你告诉他，在保证这条边有希望被留下来的同时，这条边的维修费用最大能是多少。
（或者可以说，在保证该边在最小生成树的前提下，边权最大为多少）

显然就是个最小生成树的题
对于树上边，我们要求他比环上最小非树边小
对于非树边，我们要求他比环上最大树边小
然后我们就转换成了求路径最大值和覆盖路径的问题

显然的，这题可以拿树剖切掉，太板了，但是我赛时写挂了
同时，这题可以拿倍增切掉，我们平常使用的是倍增表的合并，但是我们这题同时需要倍增表的拆分。
我们在ST表打lazytag，同时在结束时将大区间的lazytag下传到小区间
同时，可以拿dsu on tree做
我们可以搞一个差分。在u,v打一个insert标记，在lca打一个erase标记，合并时维护一个set，动态查询最小值

#include<bits/stdc++.h>
#define INF 1000000000
using namespace std;
const int N=1e5+50,M=2e6+50;
struct Edge{
	int u,v,w,id;
	bool operator<(const Edge &b){
		return w<b.w;
	}
}edge[M];
int head[N],nxt[M],to[M],id[M],W[M],num;
int father[N];
int fa[N][18],mx[N][18],lazytag[N][18];
int whichedge[N];
bool tag[M];
int dep[N],ans[M];
int n,m;
void add(int u,int v,int w,int idx){
	++num;nxt[num]=head[u];to[num]=v;W[num]=w;id[num]=idx;head[u]=num;
}
int find(int x){
	if(father[x]==x)return x;
	return father[x]=find(father[x]);
}
void dfs(int u){
	for(int i=1;i<=17;i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
		mx[u][i]=max(mx[fa[u][i-1]][i-1],mx[u][i-1]);
	}
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa[u][0])continue;
		fa[v][0]=u;
		mx[v][0]=W[i];
		dep[v]=dep[u]+1;
		whichedge[v]=id[i];
		dfs(v);
	}
}
void init(){
	for(int i=1;i<=n;i++)father[i]=i;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=17;j++)
			lazytag[i][j]=INF;
}
void modify(int u,int v,int w){
	if(dep[u]>dep[v])swap(u,v);
	for(int i=17;i>=0;i--)
		if(dep[fa[v][i]]>=dep[u]){
			lazytag[v][i]=min(lazytag[v][i],w);
			v=fa[v][i];
		}
	if(u==v)return;
	for(int i=17;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			lazytag[u][i]=min(lazytag[u][i],w);
			lazytag[v][i]=min(lazytag[v][i],w);
			u=fa[u][i];v=fa[v][i];
		}
	}
	lazytag[u][0]=min(lazytag[u][0],w);
	lazytag[v][0]=min(lazytag[v][0],w);
}
int query(int u,int v){
	int ans=0;
	if(dep[u]>dep[v])swap(u,v);
	for(int i=17;i>=0;i--)
		if(dep[fa[v][i]]>=dep[u]){
			ans=max(ans,mx[v][i]);
			v=fa[v][i];
		}
	if(u==v)return ans;
	for(int i=17;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			ans=max(ans,mx[u][i]);
			ans=max(ans,mx[v][i]);
			u=fa[u][i];v=fa[v][i];
		}
	}
	ans=max(ans,mx[u][0]);
	ans=max(ans,mx[v][0]);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);init();
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		edge[i].u=u;edge[i].v=v;edge[i].w=w;edge[i].id=i;
	}
	sort(edge+1,edge+m+1); 
	for(int i=1;i<=m;i++){
		int u=edge[i].u,v=edge[i].v,w=edge[i].w;
		int fx=find(u),fy=find(v);
		if(find(fx)!=find(fy)){
			father[fx]=fy;
			tag[i]=1;
			add(u,v,w,edge[i].id);add(v,u,w,edge[i].id);
//			printf("%d %d %d %d\n",u,v,w,i);
		}
	}
	dep[1]=1;
	dfs(1);memset(ans,-1,sizeof(ans));
	for(int i=1;i<=m;i++){
		if(!tag[i]){
			ans[edge[i].id]=query(edge[i].u,edge[i].v);
			modify(edge[i].u,edge[i].v,edge[i].w);
		}
	}
	for(int i=17;i>=1;i--){
		for(int j=1;j<=n;j++){
			lazytag[j][i-1]=min(lazytag[j][i-1],lazytag[j][i]); 
			lazytag[fa[j][i-1]][i-1]=min(lazytag[fa[j][i-1]][i-1],lazytag[j][i]);
		}
	}
	for(int i=1;i<=n;i++)
		ans[whichedge[i]]=lazytag[i][0];
//	for(int i=1;i<=n;i++)printf("?%d\n",whichedge[i]);
	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
}