今日关键字：hyk没来，窝萌缺少了成熟的思想qwq
开场看A，按照不同的数字分类讨论，fxq wa一发，lxy提示如果中心点有数字，除了8其他都挂，fxq改了之后过了
之后看到G和H都有人过，lxy看G，fxq看H，双双自闭qwq，应该是因为我俩思想都不如hyk成熟。。。
然后看G，lxy和fxq分别用dij和dfs贪心跑了n遍，还剩十分钟fxq想到hack数据，多次碰到不能到达t点的环就gg，lxy提出不走不能到t的点，反向建图跑一遍终于在4：53a掉了
fxq:HJ
lxy:FIJ
hyk:暂未补题
赛后fxq和lxy继续推H，窝萌想过一种让求和表达式最大的对应方案是最小的数和最大的数配对，次小的和次大的，......，一番叽里呱啦之后，lxy提出有些数之间的对应关系交换对结果没有影响，fxq想到把所有数按照从小到大的顺序分成前半部分和后半部分，这两个部分的数互相交换对应的数对结果没有影响。所以把原数组变成了01数组，计算最小的交换次数使得两个数组相同。在wa了一发之后，又处理了数组长度为奇数的情况，a掉了。
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=250010;
int n,a[maxn],b[maxn],c[maxn],d[maxn],aa[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
aa[i]=a[i];
}
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
int m=(n+1)/2;
for(int i=1;i<=n;i++){
c[i]=n+1-b[i];
d[i]=c[i];
}
for(int i=1;i<=n;i++){
if(a[i]<=m) a[i]=0;
else a[i]=1;
if(aa[i]<m) aa[i]=0;
else aa[i]=1;
if(c[i]<=m) c[i]=0;
else c[i]=1;
if(d[i]<m) d[i]=0;
else d[i]=1;
}
LL ans1=0;
for(int i=1,j=1;i<=n;i++){
if(a[i]==1){
while(c[j]!=1) j++;
ans1+=abs(j-i);
j++;
}
}
LL ans2=0;
for(int i=1,j=1;i<=n;i++){
if(aa[i]==1){
while(d[j]!=1) j++;
ans2+=abs(j-i);
j++;
}
}
if(n&1) printf("%lld\n",min(ans1,ans2));
else printf("%lld\n",ans1);
}
设一条边连接点，则它影响到的点为，由于所有边不交叉，可以为每条边所在区间建立优先队列，启发式合并。
#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=250010;
int n,val[maxn];
vector<int> vec[maxn],tmp;
priority_queue<LL> pq[maxn];
struct node{
int l,r,id;
bool operator < (const node& t)const{
if(l!=t.l) return l<t.l;
return r>t.r;
}
}e[maxn];
stack<node> stk;
void dfs(int u){
for(auto v: vec[u]){
dfs(v);
if(pq[v].size()>pq[u].size()) swap(pq[v],pq[u]);
vector<LL> tmp;
while(pq[v].size()){
tmp.push_back(pq[u].top()+pq[v].top());
pq[u].pop();
pq[v].pop();
}
for(auto ele:tmp){
pq[u].push(ele);
}
}
pq[u].push(val[u]);
}
int main(){
scanf("%d",&n);
e[0].l=0;
e[0].r=1000001;
e[0].id=0;
val[0]=0;
for(int i=1;i<=n;i++){
int l,r,v;
scanf("%d %d %d",&l,&r,&v);
r--;
e[i].l=l;
e[i].r=r;
e[i].id=i;
val[i]=v;
}
sort(e,e+n+1);
for(int i=n;i>=0;i--){
while(!stk.empty() && e[i].r>=stk.top().l){
vec[e[i].id].push_back(stk.top().id);
stk.pop();
}
stk.push(e[i]);
}
dfs(0);
LL ans=0;
for(int i=1;i<n;i++){
if(!pq[0].empty()){
ans+=pq[0].top();
pq[0].pop();
}
printf("%lld ",ans);
}
if(!pq[0].empty()) ans+=pq[0].top();
printf("%lld\n",ans);
}
对于操作1，2，线段树区间加乘，维护ax + b，的a、b即可；对于操作3，可由1操作反推，但如果每次枚举1操作的话会t，我们考虑把相同且连续类型的1操作装入box，对于k=0时直接枚举，k！=0时，若答案不在box内则跳过，若在box内则二分。注意若当前位置为0，而box权威k=0操作时要跳过。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(int &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int MAXN = 310000;
int q, n = 300000;
const int p = 1e9 + 7;
struct tree{
ll add, mul;
}z[4*MAXN];
ll sum[MAXN];
struct node{
int l, r, kind;
}box[MAXN];
int cnt, tot, vis[MAXN];
void build(int rt, int l, int r){
z[rt].mul = 1;
if(l == r){
z[rt].add = 0;
z[rt].mul = 1;
return ;
}
int mid = (l + r) >> 1;
build(lson), build(rson);
}
void pushdown(int rt){
if(z[rt].mul != 1){
ll k = z[rt].mul;
z[rt << 1].add = k*z[rt << 1].add%p;
z[rt << 1|1].add = k*z[rt << 1|1].add%p;
z[rt << 1].mul = k*z[rt << 1].mul%p;
z[rt << 1|1].mul = k*z[rt << 1|1].mul%p;
z[rt].mul = 1;
}
if(z[rt].add){
ll k = z[rt].add;
z[rt << 1].add = (z[rt << 1].add + k)%p;
z[rt << 1|1].add = (z[rt << 1|1].add + k)%p;
z[rt].add = 0;
}
}
void multify(int rt, int l, int r, int nowl, int nowr){
if(nowl <= l && r <= nowr){
z[rt].add = z[rt].add*2%p;
z[rt].mul = z[rt].mul*2%p;
return ;
}
int mid = (l + r) >> 1;
pushdown(rt);
if(nowl <= mid) multify(lson, nowl, nowr);
if(nowr > mid) multify(rson, nowl, nowr);
}
void addfy(int rt, int l, int r, int nowl, int nowr, int k){
if(nowl <= l && r <= nowr){
z[rt].add = (z[rt].add + k)%p;
return ;
}
int mid = (l + r) >> 1;
pushdown(rt);
if(nowl <= mid) addfy(lson, nowl, nowr, k);
if(nowr > mid) addfy(rson, nowl, nowr, k);
}
int find(int rt, int l, int r, int pos){
if(l == r)
return rt;
int mid = (l + r) >> 1;
pushdown(rt);
if(pos <= mid) return find(lson, pos);
if(pos > mid) return find(rson, pos);
}
void work(int l, int r, int x){
while(r - l > 1){
int mid = (l + r) >> 1;
if(x >= sum[r] - sum[mid]){
x -= (sum[r] - sum[mid]);
r = mid;
}
else l = mid + 1;
}
if(x >= sum[r] - sum[l])
printf("%d\n",l);
else printf("%d\n",r);
}
int main(){
re(q);
build(1, 0, n);
vis[0] = -1;
for(int i = 1;i <= q;i ++){
int op, k, g, x;
re(op);
if(op == 1){
re(k);
if(k == 0) multify(1, 0, n, 0, tot);
if(k >= 1) addfy(1, 0, n, 0, tot, k);
tot ++;
if(k == 0){
multify(1, 0, n, tot, tot);
addfy(1, 0, n, tot, tot, 1);
}
if(k != 0) vis[tot] = 1;
else vis[tot] = 0;
sum[tot] = sum[tot-1] + k;
if(vis[tot-1] != vis[tot]){
cnt ++;
box[cnt].l = box[cnt].r = tot;
box[cnt].kind = vis[tot];
}
else{
box[cnt].r = tot;
}
}
if(op == 2){
re(g), re(x);
int now = find(1, 0, n, g);
ll ans = (z[now].mul*(x-1)%p + z[now].add%p)%p;
if(ans == 0) ans = ans + x-1;
printf("%lld\n", ans%p);
}
if(op == 3){
re(x);
int flag = 0;
for(int j = cnt;j >= 1;j --){
int l = box[j].l, r = box[j].r;
if(box[j].kind == 0){
for(int k = r;k >= l;k --){
if(x == 0) break;
if(x&1){
printf("%d\n", k);
flag = 1;
break;
}
else{
x >>= 1;
}
}
if(flag) break;
}
if(box[j].kind == 1){
if(x >= sum[r] - sum[l-1]) x -= (sum[r] - sum[l-1]);
else{
work(l, r, x);
flag = 1;
break;
}
}
}
if(!flag) printf("0\n");
}
}
return 0;
}
从最小直径生成树直径中点所在边的端点开始跑dij，构造生成树。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#define ri register int
#define ll long long
#define lson rt << 1, l, mid
#define rson rt << 1|1, mid+1, r
using namespace std;
void re(int &x){
x = 0;
int b = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-') b = 1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(b == 1)
x *= -1;
}
const int maxn = 510;
const int maxm = 125000;
const ll inf = 1e17;
int n, m, midu, midv;
ll dis[maxn], d[maxn][maxn], g[maxn][maxn], ans;
int rk[maxn][maxn], len;
vector<int> vec[maxn];
void floyed(){
for(int k = 1;k <= n;k ++){
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++){
if(i == j || i == k || k == j) continue;
if(d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
bool vis[maxn];
struct node{
ll d;
int pos, pre;
operator < (const node x)const{
return d > x.d;
}
};
int pre[maxn], cnt;
struct road{
int f, to;
}qwq[maxn];
priority_queue<node>q;
void dij(){
for(int i = 1;i <= n;i ++)
dis[i] = 1e17;
dis[midu] = len;
dis[midv] = g[midu][midv] - len;
q.push((node){dis[midu], midu, 0});
q.push((node){dis[midv], midv, 0});
while(!q.empty()){
node x = q.top();
q.pop();
if(vis[x.pos]) continue;
vis[x.pos] = 1;
if(x.pos != midu && x.pos != midv)
qwq[++ cnt] = (road){x.pos, pre[x.pos]};
for(int i = 0;i < vec[x.pos].size();i ++){
int to = vec[x.pos][i];
if(dis[to] > dis[x.pos] + g[x.pos][to]){
dis[to] = dis[x.pos] + g[x.pos][to];
pre[to] = x.pos;
if(!vis[to])
q.push((node){dis[to], to, x.pos});
}
}
}
}
int main(){
re(n), re(m);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= n;j ++)
g[i][j] = d[i][j] = 1e17;
for(int i = 1;i <= m;i ++){
int x, y, z;
re(x), re(y), re(z);
vec[x].push_back(y);
vec[y].push_back(x);
g[x][y] = g[y][x] = z;
d[x][y] = d[y][x] = z;
}
for(int i = 1;i <= n;i ++)
g[i][i] = d[i][i] = 0;
floyed();
for(int i = 1;i <= n;i ++){
for(int j = 1;j <= n;j ++)
rk[i][j] = j;
for(int j = 1;j <= n;j ++){
for(int k = j+1;k <= n;k ++){
if(d[i][rk[i][j]] > d[i][rk[i][k]])
swap(rk[i][j], rk[i][k]);
}
}
}
ans = inf;
for(int u = 1;u <= n;u ++){
for(int v = 1;v <= n;v ++){
if(u == v) continue;
if(ans > (d[u][rk[u][n]] << 1)){
ans = d[u][rk[u][n]] << 1;
midu = midv = u;
}
if(ans > (d[v][rk[v][n]] << 1)){
ans = d[v][rk[v][n]] << 1;
midu = midv = v;
}
for(int las = n, i = n-1;i >= 1;i --){
if(d[v][rk[u][i]] > d[v][rk[u][las]]){
if(ans > d[u][rk[u][i]] + d[v][rk[u][las]] + g[u][v]){
ans = d[u][rk[u][i]] + d[v][rk[u][las]] + g[u][v];
len = ans/2 - d[u][rk[u][i]];
midu = u;
midv = v;
}
las = i;
}
}
}
}
printf("%lld\n", ans);
dij();
if(midu != midv) printf("%d %d\n",midu, midv);
for(int i = 1;i <= cnt;i ++)
printf("%d %d\n",qwq[i].f, qwq[i].to);
return 0;
}