【题解】CF311C

注意到 k104k \le 10^4。考虑把所有位置按模 kk 的值分成 kk 类,并按除 kk 的商分成若干段。显然,如果在第 ii 段可以到达一个属于第 jj 类的位置,那么所有在第 ii 段以后且属于第 jj 类的位置都是可以到达的。于是,只需要维护 did_i 表示属于第 ii 类的位置在哪一段第一次出现,就可以 O(1)\mathcal O(1) 地判定某个位置是否可以到达。

考虑第一种操作。考虑「向前走 xx 步」这个操作在模 kk 下意义的本质:它使得 ii 可以到达 (i+x)modk(i + x) \bmod k,但是中间要跨过 i+xk\left\lfloor\dfrac{i+x}{k}\right\rfloor 个额外的段。于是建个图:设一个源点 SS,并对于所有 0i<k0 \le i <k 连权值为 did_i 的有向边 SiS \to i,点之间按上面说的「本质」连边,从源点跑 Dijkstra,跑完之后更新 dd 即可。单次操作的时间复杂度为 O(klogk+n)\mathcal O(k \log k + n)

答案可以用 multiset 维护,操作二和三也直接在 multiset 里面操作。

// 2021.08.06 - 11:32
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define debug printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)
#define fi first
#define se second
inline int read(){
    int x=0,f=1;
    char ch='.';
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
inline void chmax(int &x,int y){x=max(x,y);}
inline void chmin(int &x,int y){x=min(x,y);}

const int MOD = 998244353;
inline int add(int x,int y){return(x+y>=MOD)?(x+y-MOD):((x+y<0)?(x+y+MOD):(x+y));}

const int MAXN = 100005, MAXM = 10005;
const int INF = 1e18 + 20;
int stO_yzhang_txdy_ddjxd_Orz, n, m, k;
int a[MAXN], c[MAXN];
int d[MAXM];
multiset<int> s;
bool in[MAXN];

inline bool ok(int x) {
	return d[x % k] <= x / k;
}

struct Node {
	int x, w;
	bool operator < (const Node& b) const {
		return w > b.w;
	}
};
int dis[MAXN];
bool vis[MAXN];
vector<Node> G[MAXN];

void dijkstra(int S) {
	memset(vis, false, sizeof(vis));
	priority_queue<Node> q;

	dis[S] = 0;
	q.push((Node) { S, 0 });
	while (!q.empty()) {
		auto p = q.top();
		q.pop();
		if (vis[p.x]) continue;
		vis[p.x] = true;

		for (auto i : G[p.x]) {
			if (vis[i.x]) continue;
			if (dis[i.x] > p.w + i.w) {
				dis[i.x] = p.w + i.w;
				q.push((Node) { i.x, dis[i.x] });
			}
		}
	}
}

inline void upd(int x) {
	for (int i = 0; i < k; i++)
		G[i].clear(), dis[i] = INF;

	for (int i = 0; i < k; i++) {
		G[i].push_back((Node){(i + x) % k, (i + x) / k});
		G[k].push_back((Node){i, d[i]});
	}

	dijkstra(k);
	for (int i = 0; i < k; i++) {
		chmin(d[i], dis[i]);
	}

	for (int i = 1; i <= n; i++) {
		if (ok(a[i]) && !in[i]) {
			in[i] = true;
			s.insert(c[i]);
		}
	}
}

signed main()

{
	stO_yzhang_txdy_ddjxd_Orz = read(), n = read(), m = read(), k = read();

	for (int i = 0; i < k; i++)
		d[i] = INF;
	d[1 % k] = 0;

	for (int i = 1; i <= n; i++) {
		a[i] = read(), c[i] = read();
		if (ok(a[i])) s.insert(c[i]), in[i] = true;
	}

	while (m--) {
		int opt = read();
		if (opt == 1) {
			int x = read();
			upd(x);
		} else if (opt == 2) {
			int x = read(), y = read();
			if (in[x]) s.erase(s.find(c[x]));
			c[x] -= y;
			if (in[x]) s.insert(c[x]);
		} else {
			if (s.empty()) cout << 0 << endl;
			else {
				cout << *prev(s.end()) << endl;
				s.erase(prev(s.end()));
			}
		}
	}
	return 0;
}