单点修改
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;const int N = 1e6;
#define lc p << 1
#define rc p << 1 | 1
struct Tree {int l, r, mx;
}tr[N * 4];void pushup(int p) {tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}
void build(int p, int l, int r) {tr[p] = {l, r, 0ll};if (l == r) return ;int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);pushup(p);
}int query(int p, int ql, int qr) {if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].mx;if (ql > tr[p].r || qr < tr[p].l) return 0;return max(query(lc, ql, qr), query(rc, ql, qr));
}void modify(int p, int x, int k) {if (tr[p].l == tr[p].r && tr[p].l == x) {tr[p].mx = k;return ;}if (x <= tr[lc].r) modify(lc, x, k);if (x >= tr[rc].l) modify(rc, x, k);pushup(p);
}int dp[N];
void solve() {int n, d; cin >> n >> d;build(1, 0ll, 500000ll);for (int i = 1; i <= n; i++) {int x; cin >> x;int l = max(0ll, x - d), r = min(500000ll, x + d);int t = query(1, l, r);dp[x] = t + 1;modify(1, x, dp[x]);}int ans = 0;for (int i = 1; i <= 5e5; i++) {ans = max(ans, dp[i]);}cout << ans << '\n';
}signed main() {IOS;// int T; cin >> T;// while (T--)solve();return 0;
}
区间修改
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;const int N = 4e5 + 10;
#define lc p << 1
#define rc p << 1 | 1
struct Tree {int l, r, sum, add, mul;
}tr[N * 4];int n, q, mod;
int a[N];
void pushup(int p) {tr[p].sum = (tr[lc].sum + tr[rc].sum) % mod;
}void build(int p, int l, int r) {tr[p] = {l, r, 0, 0, 1};if (l == r) {tr[p].sum = a[l] % mod;return ;}int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);pushup(p);
}void pushdown(int p) {tr[lc].sum = (tr[lc].sum * tr[p].mul % mod + (tr[p].add * (tr[lc].r - tr[lc].l + 1) % mod)) % mod;tr[lc].mul = (tr[lc].mul * tr[p].mul) % mod;tr[lc].add = (tr[lc].add * tr[p].mul + tr[p].add) % mod;tr[rc].sum = (tr[rc].sum * tr[p].mul % mod + (tr[p].add * (tr[rc].r - tr[rc].l + 1) % mod)) % mod;tr[rc].mul = (tr[rc].mul * tr[p].mul) % mod;tr[rc].add = (tr[rc].add * tr[p].mul + tr[p].add) % mod;tr[p].add = 0;tr[p].mul = 1;
}
void update_add(int p, int ql, int qr, int k) {if (tr[p].l > qr || tr[p].r < ql) return ;if (ql <= tr[p].l && qr >= tr[p].r) {tr[p].add = (tr[p].add + k) % mod;tr[p].sum = (tr[p].sum + (tr[p].r - tr[p].l + 1) * k) % mod;return ;}pushdown(p);int mid = tr[p].l + tr[p].r >> 1;if (ql <= mid) update_add(lc, ql, qr, k);if (qr > mid) update_add(rc, ql, qr, k);pushup(p);
}void update_mul(int p, int ql, int qr, int k) {if (tr[p].l > qr || tr[p].r < ql) return ;if (ql <= tr[p].l && qr >= tr[p].r) {tr[p].mul = tr[p].mul * k % mod;tr[p].add = tr[p].add * k % mod;tr[p].sum = tr[p].sum * k % mod;return ;}pushdown(p);int mid = tr[p].l + tr[p].r >> 1;if (ql <= mid) update_mul(lc, ql, qr, k);if (qr > mid) update_mul(rc, ql, qr, k);pushup(p);
}int query(int p, int ql, int qr) {if (tr[p].l > qr || tr[p].r < ql) return 0;if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].sum % mod;pushdown(p);int ans = 0;int mid = tr[p].l + tr[p].r >> 1;if (ql <= mid) ans += query(lc, ql, qr);if (qr > mid) ans += query(rc, ql, qr);ans %= mod;return ans;
}void solve() {cin >> n >> q >> mod;for (int i = 1; i <= n; i++) cin >> a[i];build(1, 1, n);while (q--) {int op; cin >> op;int l, r; cin >> l >> r;if (op == 1) {int k; cin >> k;update_mul(1, l, r, k);}else if (op == 2) {int k; cin >> k;update_add(1, l, r, k);}else {cout << query(1, l, r) << '\n';}}
}signed main() {IOS;// int T; cin >> T;// while (T--)solve();return 0;
}
势能线段树
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
//#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;const int N = 4e5 + 10;
#define lc p << 1
#define rc p << 1 | 1struct Tree {int l, r, sum, mx;
}tr[N * 4];
int a[N];void pushup(int p) {tr[p].sum = tr[lc].sum | tr[rc].sum;tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}void build(int p, int l, int r) {tr[p] = {l, r, a[l], a[l]};if (l == r) return ;int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);pushup(p);
}void modify(int p, int x, int v) {if (x < tr[p].l || x > tr[p].r) return ;if (tr[p].l == tr[p].r && tr[p].l == x) {tr[p].sum = v;tr[p].mx = v;return ;}int mid = tr[p].l + tr[p].r >> 1;if (x <= mid) modify(lc, x, v);if (x > mid) modify(rc, x, v);pushup(p);
}void update(int p, int ql, int qr, int v) {if (tr[p].l > qr || tr[p].r < ql) return ;if (tr[p].l == tr[p].r) {tr[p].sum &= v;tr[p].mx &= v;return ;}if ((tr[p].sum & v) == tr[p].sum) return ;update(lc, ql, qr, v);update(rc, ql, qr, v);pushup(p);
}int query(int p, int ql, int qr) {if (tr[p].l > qr || tr[p].r < ql) return 0;if (ql <= tr[p].l && qr >= tr[p].r) return tr[p].mx;int ans = 0;int mid = tr[p].l + tr[p].r >> 1;if (ql <= mid) ans = max(ans, query(lc, ql, qr));if (qr > mid) ans = max(ans, query(rc, ql, qr));return ans;
}int read() {int x; scanf("%lld", &x);return x;
}char op[4];
void solve() {int n, m; n = read(), m = read();for (int i = 1; i <= n; i++) a[i] = read();build(1, 1, n);while (m--) {scanf("%s", op);if (op[0] == 'A') {int l, r, v; l = read(), r = read(), v = read();update(1, l, r, v);}else if (op[0] == 'U') {int x, v; x = read(), v = read();modify(1, x, v);}else {int l, r; l = read(), r = read();cout << query(1, l, r) << '\n';}}
}signed main() {//IOS;// int T; cin >> T;// while (T--)solve();return 0;
}
主席树
区间第k大
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr);
#define rep(i, x, y) for(int i=(x), _=(y);i<=_;i++)
#define rrep(i, x, y) for(int i=(x), _=(y);i>=_;i--)
#define all(x) x.begin(),x.end()
#define PII pair<int, int>
#define x first
#define y second
#define ll long long
#define int long long
#define endl '\n'
const int inf = LONG_LONG_MAX;
using i64 = long long;const int N = 2e5 + 10;
#define lc(x) tr[x].ch[0]
#define rc(x) tr[x].ch[1]
struct Tree {int ch[2];int s;
}tr[N * 22];
int root[N];
int a[N];
int idx;void build(int &p, int l, int r) {p = ++idx;if (l == r) return ;int mid = l + r >> 1;build(lc(p), l, mid);build(rc(p), mid + 1, r);
}void insert(int x, int &y, int l, int r, int v) {y = ++idx;tr[y] = tr[x];tr[y].s++;if (l == r) return ;int mid = l + r >> 1;if (v <= mid) insert(lc(x), lc(y), l, mid, v);else insert(rc(x), rc(y), mid + 1, r, v);
}int query(int x, int y, int l, int r, int k) {if (l == r) return l;int mid = l + r >> 1;int sum = tr[lc(y)].s - tr[lc(x)].s;if (sum >= k) return query(lc(x), lc(y), l, mid, k);else return query(rc(x), rc(y), mid + 1, r, k - sum);
}int arr[N];
void solve() {int n, m; cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> a[i];arr[i] = a[i];} build(root[0], 1, n);sort(arr + 1, arr + 1 + n);for (int i = 1; i <= n; i++) {a[i] = lower_bound(arr + 1, arr + 1 + n, a[i]) - arr;}for (int i = 1; i <= n; i++) {insert(root[i - 1], root[i], 1, n, a[i]);}while (m--) {int l, r, k; cin >> l >> r >> k;int t = query(root[l - 1], root[r], 1, n, k);cout << arr[t] << '\n';}
}signed main() {IOS;// int T; cin >> T;// while (T--)solve();return 0;
}
主席树二分
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define PII pair<int, int>
#define x first
#define y second
#define endl '\n'inline int read() {int c; cin >> c; return c;}
inline void readn(int a[], int n) {for_each(a + 1, a + n + 1, [](int &x) {cin >> x;});
}
inline void writen(int a[], int n) {for_each(a + 1, a + n + 1, [](int &x) { cout << x << ' '; });cout << endl;
}
template<typename T, typename... Args>
void write(const T &first, const Args &...args) {cout << first;((cout << ' ' << args), ...);cout << endl;
}
template<typename T, typename... Args>
void ewrite(const T& first, const Args&... args) {cerr << '*';cerr << first;((cerr << ' ' << args), ...);cerr << endl;
}
char out[2][10] = {"No", "Yes"};
const double eps = 1e-6;
const int N = 1e6 + 10;
const int M = N << 1;
const int mod = 998244353;/* next is main_solve */
int n;
int a[N];struct node {int l, r, sum;
} o[N * 30];
int rt[N];
int tot;
int add(int x, int l, int r, int v) {int t = ++tot;o[t] = o[x];o[t].sum++;if (l == r)return t;int mid = (l + r) / 2;if (v <= mid)o[t].l = add(o[t].l, l, mid, v);elseo[t].r = add(o[t].r, mid + 1, r, v);return t;
}int asksum(int x, int l, int r, int ql, int qr)
{if (x == 0)return 0;if (ql <= l && r <= qr)return o[x].sum;int mid = l + r >> 1;if (ql <= mid && qr > mid)return asksum(o[x].l, l, mid, ql, qr) + asksum(o[x].r, mid + 1, r, ql, qr);else if (ql <= mid)return asksum(o[x].l, l, mid, ql, qr);elsereturn asksum(o[x].r, mid + 1, r, ql, qr);
}
int ask(int x, int l, int r, int cnt)
{if (l == r)return l;int mid = l + r >> 1;if (o[o[x].l].sum >= cnt)return ask(o[x].l, l, mid, cnt);elsereturn ask(o[x].r, mid + 1, r, cnt - o[o[x].l].sum);}
int ask(int beg, int i, int k)
{int sum = o[rt[i]].sum; //总的大于等于i的位置的数量int suml;if (beg == 1)suml = 0;elsesuml = asksum(rt[i], 1, n, 1, beg - 1);//beg前面有几个大于等于iif (sum - suml < k) //如果剩下的数量不足k个则无法升级，返回n+1return n + 1;return ask(rt[i], 1, n, suml + k); //区间里第一个等于suml+k的位置
}vector<int> sb[N];
vector<int> pos[N];void solve() {n = read();int q;q = read();readn(a, n);for (int i = 1; i <= n; i++) {sb[a[i]].pb(i);}for (int i = 200000; i >= 1; i--) {rt[i] = rt[i + 1];for (auto x : sb[i]) {rt[i] = add(rt[i], 1, n, x);}}for (int k = 1; k <= n; k++) {for (int l = 1, r, i = 1; l <= n; i++) {r = ask(l, i, k);pos[k].pb(r);l = r + 1;}}while (q--) {int p, k;p = read(), k = read();int t = lower_bound(all(pos[k]), p) - pos[k].begin() + 1;if (a[p] >= t) {cout << "YES\n";}else {cout << "NO\n";}}
}void cloud_fly() {// int t;// cin >> t;// while (t--)solve();
}signed main() {ios::sync_with_stdio(false), cin.tie(nullptr);cloud_fly();return 0;
}
扫描线
扫描线求面积
#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 1e5 + 10;struct line{int x1, x2, y, tag;
}L[N * 2];
bool cmp(line l1, line l2) {return l1.y < l2.y;
}
int X[N * 2];#define lc p << 1
#define rc p << 1 | 1
struct Tree{int l, r;int cnt, len;
}tr[N * 16];void pushup(int p) {int l = tr[p].l, r = tr[p].r;if (tr[p].cnt > 0) tr[p].len = X[r + 1] - X[l];else tr[p].len = tr[lc].len + tr[rc].len;
}
void build(int p, int l, int r) {tr[p] = {l, r, 0, 0};if (l == r) return ;int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);
}void update(int p, int ql, int qr, int k) {if (tr[p].r < ql || tr[p].l > qr) return ;if (tr[p].l >= ql && tr[p].r <= qr) {tr[p].cnt += k;pushup(p);return ;}update(lc, ql, qr, k);update(rc, ql, qr, k);pushup(p);
}void solve() {int n; cin >> n;for (int i = 1; i <= n; i++) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;L[i] = {x1, x2, y1, 1};L[n + i] = {x1, x2, y2, -1};X[i] = x1;X[n + i] = x2;}n *= 2;sort(L + 1, L + 1 + n, cmp);sort(X + 1, X + 1 + n);int m = unique(X + 1, X + 1 + n) - X - 1;build(1, 1, m - 1);int ans = 0;for (int i = 1; i < n; i++) {int ql = lower_bound(X + 1, X + 1 + m, L[i].x1) - X;int qr = lower_bound(X + 1, X + 1 + m, L[i].x2) - X;update(1, ql, qr - 1, L[i].tag);ans += 1ll * tr[1].len * (L[i + 1].y - L[i].y);}cout << ans << '\n';
}signed main() {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0);// int T; cin >> T;// while (T--) solve();return 0;
}
扫描线求周长
#include <bits/stdc++.h>
using namespace std;#define int long long
const int N = 5e3 + 10;
int X[N * 2];
struct line{int x1, x2, y, tag;bool operator< (const line t) {if (y == t.y) return tag > t.tag;return y < t.y;}
}L[N * 16];struct Tree{int l, r;int cnt, len; int lcover, rcover, sum;
}tr[N * 8];
#define lc p << 1
#define rc p << 1 | 1void build(int p, int l, int r) {tr[p] = {l, r, 0, 0, 0, 0, 0};if (l == r) return ;int mid = l + r >> 1;build(lc, l, mid);build(rc, mid + 1, r);
}void pushup(int p) {int l = tr[p].l, r = tr[p].r;if (tr[p].cnt) {tr[p].len = X[r + 1] - X[l];tr[p].sum = 2;tr[p].lcover = tr[p].rcover = 1;}else {tr[p].len = tr[lc].len + tr[rc].len;tr[p].sum = tr[lc].sum + tr[rc].sum;tr[p].lcover = tr[lc].lcover;tr[p].rcover = tr[rc].rcover;if (tr[lc].rcover && tr[rc].lcover) {tr[p].sum -= 2;} }
}void update(int p, int ql, int qr, int k) {if (tr[p].r < ql || tr[p].l > qr) return ;if (tr[p].l >= ql && tr[p].r <= qr) {tr[p].cnt += k;pushup(p);return ;}update(lc, ql, qr, k);update(rc, ql, qr, k);pushup(p);
}void solve() {int n; cin >> n;for (int i = 1; i <= n; i++) {int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;X[i] = x1;X[n + i] = x2;L[i] = {x1, x2, y1, 1};L[n + i] = {x1, x2, y2, -1};}n *= 2;sort(X + 1, X + 1 + n);int m = unique(X + 1, X + 1 + n) - X - 1;sort(L + 1, L + 1 + n);build(1, 1, m - 1);int ans = 0;int lst = 0;for (int i = 1; i < n; i++) {int l = lower_bound(X + 1, X + 1 + m, L[i].x1) - X;int r = lower_bound(X + 1, X + 1 + m, L[i].x2) - X;update(1, l, r - 1, L[i].tag);ans += abs(tr[1].len - lst);lst = tr[1].len;ans += tr[1].sum * (L[i + 1].y - L[i].y);}ans += L[n].x2 - L[n].x1;cout << ans << '\n';
}signed main() {//freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0);// int T; cin >> T;// while (T--) solve();return 0;
}
