气崩了气崩了，本来还用zybuluo.com，结果他访问不了了，算了，回到我的Typora和cnblogs了。
模拟赛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条双向道路连接。 每条双向道路都有一个维修费用。
国王想要去掉尽可能多的边，使得留下来的边依旧能使王国的任意两个城市之间都有经过一条或多条边的路径。在所有的方案中， 国王希望留下来的边的维修费用之和最小。
现在，国王准备调整一些边的维修费用来影响最后留下的边的结果。对于每条边，他希望你告诉他，在保证这条边有希望被留下来的同时，这条边的维修费用最大能是多少。
（或者可以说，在保证该边在最小生成树的前提下，边权最大为多少）
显然就是个最小生成树的题
对于树上边，我们要求他比环上最小非树边小
对于非树边，我们要求他比环上最大树边小
显然的，这题可以拿树剖切掉
#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]);
}