坑 -2
填坑计划持续进行中咻

Problem

逛公园

https://www.luogu.org/problemnew/show/P3953

列队

https://www.luogu.org/problemnew/show/P3960

Solution

逛公园

这里讲的挺好：https://zhzh2001.github.io/2017/12/02/noip2017-solution/

列队

考虑每次操作，会往一行最后一个加人和最后一列的最后一个加人
于是维护 n + 1 棵线段树（动态开点）
然后查询线段树的第 k 大值，并把第 k 大值减去。

这里有几个小细节，一是一开始权值不是 0 而是 1，这样不好维护。
那么我们假设一开始权值都是 0，然后删掉的话就把权值改成 -1，就好维护了。

二是对于 n 棵线段树的查询，如果查到的是未开点的部分，那么对于这个点手动算坐标。如果查到了开点部分，直接返回插入的坐标。对于最后一列的线段树，直接暴力插入初始化就行。

三是爆 int 注意。

啊以及空间复杂度是个玄学来着。

Code

逛公园

// Code by ajcxsu
// Problem: park

#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

const int N=1e5+2, M=5e5+2, K=51;
int h[N], to[M], nexp[M], W[M], p=1;
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
typedef long long ll;
int f[N][K];
int T, n, m, k, mo;

int d1[N], d2[N];
char S[N];
typedef pair<int, int> mpair;
priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
void dij(int dist[], int s, int d) {
    memset(dist, 0x3f, sizeof(d1)), CLR(S);
    dist[s]=0;
    pq.push(mpair(0, s));
    int na;
    while(!pq.empty()) {
        na=pq.top().second, pq.pop();
        if(S[na]) continue;
        S[na]=1;
        for(int u=h[na];u;u=nexp[u])
            if(u%2==d && dist[to[u]]>dist[na]+W[u])
                dist[to[u]]=dist[na]+W[u], pq.push(mpair(dist[to[u]], to[u]));
    }
}

char vis[N][K], flag;
int dfs(int x, int nk) {
    flag=vis[x][nk];
    if(f[x][nk]!=-1) return f[x][nk];
    vis[x][nk]=1, f[x][nk]=(x==n);
    for(int u=h[x]; u && !flag; u=nexp[u])
        if((u&1) && nk+d1[x]-d1[to[u]]+W[u]<=k && d1[x]+nk+d2[to[u]]+W[u]<=d1[n]+k)
            f[x][nk]=(f[x][nk]+dfs(to[u], nk+d1[x]-d1[to[u]]+W[u]))%mo;
    vis[x][nk]=0;
    return f[x][nk];
}

void ini() { CLR(h), p=1, memset(f, -1, sizeof(f)), flag=0; }
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>T;
    while(T--) {
        cin>>n>>m>>k>>mo, ini();
        int u, v, w;
        for(int i=0;i<m;i++) cin>>u>>v>>w, ins(u, v, w), ins(v, u, w);
        dij(d1, 1, 1), dij(d2, n, 0);
        int ans=dfs(1, 0); ans=flag?-1:ans;
        cout<<ans<<endl;
    }
    return 0;
}

列队

// Code by ajcxsu
// Problem: sylvia

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=3e5+10, M=1e7+10;
struct Node *nil;
struct Node {
    Node *ls, *rs;
    ll v;
    int c;
} *nd[N], *co, po[M], *pp=po;
void ini() { nil=pp++, nil->ls=nil->rs=nil, nil->v=0, nil->c=0, fill(nd, nd+N, nil), co=nil; }

void updata(Node *&x, int l, int r, int d, int v, ll w) {
    if(x==nil) { Node *nd=pp++; *nd=*x, x=nd; }
    x->c+=v;
    if(l==r) {x->v=w; return;}
    int mid=(l+r)>>1;
    if(d<=mid) updata(x->ls, l, mid, d, v, w);
    else updata(x->rs, mid+1, r, d, v, w);
}

pair<int, ll> query(Node *x, int l, int r, int k) {
    if(l==r) return pair<int, ll>(l, x->v);
    int mid=(l+r)>>1;
    if(k<=mid-l+1+x->ls->c) return query(x->ls, l, mid, k);
    else return query(x->rs, mid+1, r, k-(mid-l+1+x->ls->c));
}

int len[N], colen;
int main() {
    ios::sync_with_stdio(false), cin.tie(0), ini();
    int n, m, q, k;
    cin>>n>>m>>q, k=max(n, m)+q+1, fill(len, len+N, m-1), colen=n;
    for(int i=1;i<=n;i++) updata(co, 1, k, i, 0, 1ll*i*m);
    int x, y;
    ll wh;
    pair<int, ll> pr, pr2;
    while(q--) {
        cin>>x>>y;
        if(y==m) {
            pr=query(co, 1, k, x);
            cout<<pr.second<<endl;
            updata(co, 1, k, pr.first, -1, 0), updata(co, 1, k, ++colen, 0, pr.second);
        }
        else {
            pr=query(nd[x], 1, k, y), wh=pr.second;
            if(!wh) cout<<(wh=1ll*(x-1)*m+pr.first)<<endl;
            else cout<<wh<<endl;
            pr2=query(co, 1, k, x);
            len[x]++, updata(nd[x], 1, k, pr.first, -1, 0);
            updata(nd[x], 1, k, len[x], 0, pr2.second);
            updata(co, 1, k, pr2.first, -1, 0), updata(co, 1, k, ++colen, 0, wh);
        }
    }
    return 0;
}