6.22 模拟赛
A 城市建设
题意：给定n个点和m条边和q个询问，点有点权，这些边分别在(t_i)时刻出现，求在某时刻所有连通的点对点权之积的和
解：将修改按时间排序，枚举修改，每次合并连通块，处理答案，实现用并查集就可以
注意答案是所有集合的答案之和，所以在合并的时候要处理整体的答案
最后枚举的时候要按询问枚举，不然会RE放屁
“我今天就是要把s2oj交爆在这里！！！”
码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define re register
using namespace std;
const int INF=0x3f3f3f3f,N=100010;
ll f[N],sum[N];
ll n,m,q;
ll val[N];
ll anss=0,ans[N];
struct query{
ll id,pos;
}que[N];
struct ch{
ll t,x,y;
}upd[N];
bool cmp1(ch a,ch b){
return a.t<b.t;
}
bool cmp2(query a,query b){
return a.pos<b.pos;
}
int find(ll a){
if(f[a]!=a) return f[a]=find(f[a]);
return a;
}
void merge(ll a,ll b){
re ll x=find(a),y=find(b);
if(x==y) return;
f[x]=y,anss+=sum[x]*sum[y],sum[y]+=sum[x];
}
inline ll read(){
ll x=0,y=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
int main(){
n=read();
m=read();
q=read();
for(re ll i=1;i<=n;i++) sum[i]=read(),f[i]=i;
for(re ll i=1;i<=m;i++){
upd[i].t=read();
upd[i].x=read();
upd[i].y=read();
}
sort(upd+1,upd+1+m,cmp1);
for(re ll i=1;i<=q;i++) que[i].pos=read(),que[i].id=i;
sort(que+1,que+1+q,cmp2);
ll qq=1;
for(re ll i=1;i<=m;i++){
while(qq<=q&&que[qq].pos<upd[i].t) ans[que[qq].id]=anss,qq++;
merge(upd[i].x,upd[i].y);
}
while(qq<=q) ans[que[qq].id]=anss,qq++;
for(re ll i=1;i<=q;i++) printf("%lld
",ans[i]);
return 0;
}
B 矩形2
题意：有n个矩形，所有矩形的其中一条边在x轴上，求所有矩形所覆盖到的面积
解：可以用扫描线，但是发现矩形们的其中一条边都在一条直线上，也就是高度的基准线一样，我们可以将竖直边进行排序，扫一遍，用堆来维护当前区间的最大高度，处理出每两根竖直线之间矩形的面积，实现可用可删堆
码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int INF=0x3f3f3f3f,N=100010;
int n,pos=0;
ll ans=0;
struct ss{
ll x;
int id,h;
bool typ;
}op[N];
bool cmp(ss a,ss b){
return (a.x==b.x)?(a.typ?0:1):a.x<b.x;
}
inline int read(){
int x=0,y=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
struct PQ{
priority_queue<int> val,delv;
void clear(){priority_queue<int> nv,nd;swap(nv,val);swap(nd,delv);}
void pop(int x){delv.push(x);}
void push(int x){val.push(x);}
int top(){
while(!delv.empty()&&delv.top()==val.top())
delv.pop(),val.pop();
return val.empty()?0:val.top();
}
}heap;
int main(){
n=read();
for(int i=1;i<=n;i++){
op[2*i-1].x=read(),op[2*i].x=read(),op[2*i-1].h=op[2*i].h=read();
op[2*i-1].typ=0,op[2*i].typ=1;
}
sort(op+1,op+2*n+1,cmp);
heap.clear();
for(int i=1;i<=2*n;i++){
if(i>=2) ans+=(op[i].x-op[i-1].x)*heap.top();
if(!op[i].typ){
pos++;
heap.push(op[i].h);
}else{
pos--;
heap.pop(op[i].h);
}
}
cout<<ans<<endl;
return 0;
}
C 新型计算机
题意：一个序列，从第一个开始遍历，读到几就再往后读几个数，若刚好读完最后一个数，那么这个序列就是一个合法序列，现给出一个不合法序列，进行把序列里每一个数都加上或减去一个数，使之变为合法的，求这个数的绝对值最小是多少
解：可最短路可DP，最短路建图题，树状数组优化DP，我写的最短路
码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int INF=0x3f3f3f3f,N=1000010;
int e[4*N],ne[4*N],idx,h[N],w[4*N],n,ls[N],rs[N];
inline int read(){
int x=0,y=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
namespace dijkstra{
int dist[N];
bool vis[N];
int dijkstra(int st,int ed){
memset(dist,0x3f,sizeof dist);
priority_queue<pii,vector<pii>,greater<pii> > q;
dist[st]=0;
q.push(make_pair(0,st));
while(q.size()){
pii op=q.top();
q.pop();
int dis=op.first,ver=op.second;
if(vis[ver]) continue;
vis[ver]=1;
for(int i=h[ver];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
q.push(make_pair(dist[j],j));
}
}
}
if(dist[ed]==0x3f) return -1;
return dist[ed];
}
}
int main(){
memset(h,-1,sizeof h);
n=read();
for(int i=1,k;i<=n;i++){
k=read();
if(i+k<=n) add(i,i+k+1,0);
else add(i,n+1,i+k-n);
for(int j=i+1;j<=i+k+1&&j<=n&&!ls[j];j++) ls[j]=1,add(j,j-1,1);
for(int j=i+k+1;j<=n&&!rs[j];j++) rs[j]=1,add(j,j+1,1);
}
ll ans=dijkstra::dijkstra(1,n+1);
printf("%lld
",ans);
return 0;
}
D 邮箱
简化版题意：给你俩序列，给你一堆询问，询问是俩序列里的两段区间，问这两段区间里相同数/个数的乘积之和除以
第二段区间长度
解：莫队搞，和这个一样，把一个询问拆成四个询问，每个询问都形如 (get(pos_1,x) imes get(pos_2,x)) ，然后排序莫队扫就可以了，还有数组开小了会有神奇的效果
码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define int long long
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f,N=100010;
int n,m,a[N],b[N],q,cnt=0,be[N],op;
int cntl[N],cntr[N],res=0,l,r,ans[10*N];
int ans1[10*N];
struct query{
int ql,qr,id,typ;
query(int l=0,int r=0,int id=0,int typ=0):ql(l),qr(r),id(id),typ(typ){}
}que[40*N];
bool cmp(query a,query b){
return (be[a.ql]==be[b.ql])?a.qr<b.qr:a.ql<b.ql;
}
inline ll read(){
ll x=0,y=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') y=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*y;
}
void movel(int t){
if(t==1){
l++;
++cntl[a[l]];
res+=cntr[a[l]];
}else{
--cntl[a[l]];
res-=cntr[a[l]];
l--;
}
}
void mover(int t){
if(t==1){
r++;
++cntr[b[r]];
res+=cntl[b[r]];
}else{
--cntr[b[r]];
res-=cntl[b[r]];
r--;
}
}
ll gcd(ll a,ll b){
return b==0ll?a:gcd(b,a%b);
}
signed main(){
n=read();m=read();
op=sqrt(n);
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=read();
q=read();
for(int i=1;i<=q;i++){
int q1,q2,q3,q4;
q1=read(),q2=read(),q3=read(),q4=read();
que[++cnt]=query(q2,q4,i,1);
que[++cnt]=query(q2,q3-1,i,-1);
que[++cnt]=query(q1-1,q4,i,-1);
que[++cnt]=query(q1-1,q3-1,i,1);
ans1[i]=q4-q3+1;
}
for(int i=1;i<=n;i++) be[i]=i/op+1;
sort(que+1,que+1+cnt,cmp);
for(int i=1;i<=cnt;i++){
while(l>que[i].ql) movel(-1);
while(r<que[i].qr) mover(1);
while(l<que[i].ql) movel(1);
while(r>que[i].qr) mover(-1);
if(que[i].typ==1) ans[que[i].id]+=res;
else ans[que[i].id]-=res;
}
for(int i=1;i<=q;i++){
int g=gcd(ans[i],ans1[i]);
printf("%lld %lld
",ans[i]/g,ans1[i]/g);
//printf("%d
",ans[i]);
}
return 0;
}