题目ID：3592必做题100分
时间限制: 200ms
空间限制: 131072kB
如题
第一行输入一个整数nn
第二行输入nn个整数
输出字典序最小的最长上升子序列
10
6 7 1 8 2 9 3 10 4 5
1 2 3 4 5
1<=n<=1000001<=n<=100000
样例都没过，怎么二分啊?
\sin \alpha+\beta = \sin \alpha \cos \beta + \cos \alpha \sin \beta
感觉和导弹拦截很像导弹拦截的思路是贪心+二分以此来达到O(n log n)的效果所以这一题可以模仿着来进行贪心+二分但我也不太会qwq
#include<bits/stdc++.h>
using std::swap;const int maxn = 100005;int a[maxn], b[maxn], idx[maxn], top[maxn], fa[maxn], son[maxn], SegTree[maxn << 2], lazy[maxn << 2], siz_tree[maxn], depth[maxn];int N, M;struct Edge {int to, nxt;}edge[maxn << 1];int num_edge, head[maxn], root, MOD;void AddEdge(int from, int to) {edge[num_edge].to = to;edge[num_edge].nxt = head[from];head[from] = num_edge;num_edge++;}void dfs1(int nd, int f, int deep) {fa[nd] = f;depth[nd] = deep;siz_tree[nd] = 1;int max_son = -1;for (int i = head[nd]; i != -1; i = edge[i].nxt) {int j = edge[i].to;if (j == fa[nd]) continue;dfs1(j, nd, deep + 1);siz_tree[nd] += siz_tree[j];if (siz_tree[j] > max_son) {max_son = siz_tree[j];son[nd] = j;}}}int cnt = 0;void dfs2(int nd, int topf) {idx[nd] = ++cnt;b[cnt] = a[nd];top[nd] = topf;if (!son[nd]) return ;dfs2(son[nd], topf);for (int i = head[nd]; i != -1; i = edge[i].nxt) {int j = edge[i].to;if (j == fa[nd] || j == son[nd]) continue;dfs2(j, j);}}void PushUp(int nd) {SegTree[nd] = (SegTree[nd << 1] + SegTree[nd << 1 | 1]) % MOD;}void Build(int nd, int l, int r) {if (l == r) {SegTree[nd] = b[l];return ;}int mid = (l + r) >> 1;Build(nd << 1, l, mid);Build(nd << 1 | 1, mid + 1, r);PushUp(nd);}void PushDown(int nd, int ln, int rn) {if (lazy[nd]) {lazy[nd << 1] += lazy[nd];lazy[nd << 1 | 1] += lazy[nd];SegTree[nd << 1] = (SegTree[nd << 1] + ln * lazy[nd]) % MOD;SegTree[nd << 1 | 1] = (SegTree[nd << 1 | 1] + rn * lazy[nd]) % MOD;lazy[nd] = 0;}}void Update(int nd, int l, int r, int L, int R, int val) {if (L <= l && r <= R) {SegTree[nd] = (SegTree[nd] + (r - l + 1) * val) % MOD;lazy[nd] += val;return ;}int mid = (l + r) >> 1;PushDown(nd, mid - l + 1, r - mid);if (L <= mid) Update(nd << 1, l, mid, L, R, val);if (R > mid) Update(nd << 1 | 1, mid + 1, r, L, R, val);PushUp(nd);}int Query(int nd, int l, int r, int L, int R) {if (L <= l && r <= R) {return SegTree[nd] % MOD;}int mid = (l + r) >> 1;PushDown(nd, mid - l + 1, r - mid);int ans = 0;if (L <= mid) ans = (ans + Query(nd << 1, l, mid, L, R)) % MOD;if (R > mid) ans = (ans + Query(nd << 1 | 1, mid + 1, r, L, R)) % MOD;return ans;}void line_Add(int L, int R, int val) {val %= MOD;while (top[L] != top[R]) {if (depth[top[L]] < depth[top[R]]) swap(L, R);Update(1, 1, N, idx[top[L]], idx[L], val);L = fa[top[L]];}if (depth[L] > depth[R]) swap(L, R);Update(1, 1, N, idx[L], idx[R], val);}int line_Query(int L, int R) {int ans = 0;while (top[L] != top[R]) {if (depth[top[L]] < depth[top[R]]) swap(L, R);ans += Query(1, 1, N, idx[top[L]], idx[L]);ans %= MOD;L = fa[top[L]];}if (depth[L] > depth[R]) swap(L, R);ans += Query(1, 1, N, idx[L], idx[R]);ans %= MOD;return ans;}void tree_Add(int nd, int val) {Update(1, 1, N, idx[nd], idx[nd] + siz_tree[nd] - 1, val);}int tree_Query(int nd) {return Query(1, 1, N, idx[nd], idx[nd] + siz_tree[nd] - 1) % MOD;}int read() {int x = 0, f = 1;char ch = getchar();while (ch > '9' || ch < '0') {if (ch == '-') f = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return (x * f);}int main() {memset(head, -1, sizeof(head));N = read(); M = read(); root = read(); MOD = read();for (int i = 1; i <= N; i++) a[i] = read();for (int i = 1; i < N; i++) {int x = read(), y = read();AddEdge(x, y);AddEdge(y, x);}dfs1(root, 0, 1);dfs2(root, root);Build(1, 1, N);while (M--) {int x, y, z, w;x = read();switch (x) {case 1:y = read(); z = read(); w = read();line_Add(y, z, w);break;case 2:y = read(); z = read();printf("%d\n", line_Query(y, z));break;case 3:y = read(); z = read();tree_Add(y, z);break;case 4:y = read();printf("%d\n", tree_Query(y));break;default:break;}}}