注意到 。考虑把所有位置按模 的值分成 类,并按除 的商分成若干段。显然,如果在第 段可以到达一个属于第 类的位置,那么所有在第 段以后且属于第 类的位置都是可以到达的。于是,只需要维护 表示属于第 类的位置在哪一段第一次出现,就可以 地判定某个位置是否可以到达。
考虑第一种操作。考虑「向前走 步」这个操作在模 下意义的本质:它使得 可以到达 ,但是中间要跨过 个额外的段。于是建个图:设一个源点 ,并对于所有 连权值为 的有向边 ,点之间按上面说的「本质」连边,从源点跑 Dijkstra,跑完之后更新 即可。单次操作的时间复杂度为 。
答案可以用 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;
}