preamble
Algorithmic competition questions examine the contestant's choice of data structures and clever combination of algorithms, and data structures in which the line tree plays a crucial role, and recently (end of CSP) in hfu's arrangement we need to get a week's worth of ds on our own, hence this marvelous blog.
Line Tree Basics
It seems to me that a line tree is really just an array with a fewaddedpoints, which are used to maintain the information in the original array, to which some points are added to maintain thePreviously added pointsThe information of the array is then moved up one layer at a time until there is only one point, which manages the entire array. The management relationship between these points also forms a tree, so it is a line tree.
Then consider these points that are added, and if they are random, the worst case scenario might be stuck as something mysterious, so we'll let the first layer maintain two points, and the second layer maintain four points, so that we'll only build out the\(\log\) layer and the number of nodes added is\(O(n)\) The. This gives the line tree a very elegant property and calls it a true line tree.
For maintaining information with a line segment tree, we don't have to change all the relevant nodes at each modification operation, but we do need to know where we should go to modify. For example, if I'm walking up the tree and I come to an interval\([l,r]\)If this interval is contained by the modified interval, this means that I need to modify this whole interval, but direct modification is\(O(len)\) of the interval, at which point we can go ahead and write down the modification in this place and wait until I query the interval to deal with it. The intervals found in the line tree in this way are\(O(\log)\) s, so the normal modification is to find the interval plus the\(O(1)\) Marking.
And query and modify the same way, are walking in the tree every time you hit an interval can be all counted into the contribution to directly add the contribution, otherwise continue to go down, but in the modification and query need to pay attention to devolution of the previous markers, which is InextWhen I walk to a labeled node I will perform some operations on it, and the probability is that the two intervals of the original labeling and the current operation are different, so we need to decentralize the previous labeling before the operation.
Then put in two courses of plates.
P3372 [Template] Line Tree 1
We can build out the line tree, the process is a traversal of the tree process, just to the leaves of the tree (that is, the original array) when you need to save the information and then passed back layer by layer. Modification and query will not be repeated here.
void upd(int x){
s[x] = s[ls] + s[rs];
}
void bld(int x, int l, int r){
if(l == r)return (void)(s[x] = a[l]);
int mid = l + r >> 1;
bld(ls, l, mid), bld(rs, mid + 1, r);
upd(x);
}
void pd(int x, int l, int r){
if(! tg[x])return; int mid = l + r >> 1;
tg[ls] += tg[x], tg[rs] += tg[x];
s[ls] += tg[x] * (mid - l + 1);
s[rs] += tg[x] * (r - mid);
return (void)(tg[x] = 0);
}
void mdf(int x, int l, int r, int ql, int qr, ll y){
if(ql <= l and r <= qr)return (void)(s[x] += y * (r - l + 1), tg[x] += y);
int mid = l + r >> 1; pd(x, l, r);
if(ql <= mid)mdf(ls, l, mid, ql, qr, y);
if(mid < qr)mdf(rs, mid + 1, r, ql, qr, y);
upd(x);
}
ll qry(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return s[x];
int mid = l + r >> 1; ll res = 0; pd(x, l, r);
if(ql <= mid)res = qry(ls, l, mid, ql, qr);
if(mid < qr)res += qry(rs, mid + 1, r, ql, qr);
return res;
}
P3373 [Template] Line Tree 2
At this point with the multiplication operation modification and devolution seems to become complicated, at this point we need to first analyze the priority of the different operations.
First of all we must be marking separately for multiplication and addition, and then for an addition marker, it means to let the interval add a number, if we add it directly then the multiplication marker will be affected. It must be wrong to add the multiplication marker, so we should decentralize it. Notice that multiplication has a higher priority than addition, so when delegating let the multiplication marker go first.
If there is a multiplication marker, then the addition marker in the previous interval should also be multiplied by it, because of the law of multiplicative distribution. So the multiplication just changes all the way around.
void upd(int x){
s[x] = (s[ls] + s[rs]) % p;
}
void bld(int x, int l, int r){
tg2[x] = 1;
if(l == r)return (void)(s[x] = a[l]);
int mid = l + r >> 1;
bld(ls, l, mid), bld(rs, mid + 1, r);
upd(x);
}
void pd(int x, int l, int r){
int mid = l + r >> 1;
tg1[ls] = (tg1[ls] * tg2[x] + tg1[x]) % p, tg1[rs] = (tg1[rs] * tg2[x] + tg1[x]) % p;
s[ls] = (s[ls] * tg2[x] + tg1[x] * (mid - l + 1)) % p;
s[rs] = (s[rs] * tg2[x] + tg1[x] * (r - mid)) % p;
tg2[ls] = tg2[ls] * tg2[x] % p;
tg2[rs] = tg2[rs] * tg2[x] % p;
return (void)(tg1[x] = 0, tg2[x] = 1);
}
void mdf1(int x, int l, int r, int ql, int qr, ll y){
if(ql <= l and r <= qr)return (void)(s[x] = y * s[x] % p, tg2[x] = tg2[x] * y % p, tg1[x] = tg1[x] * y % p);
int mid = l + r >> 1; pd(x, l, r);
if(ql <= mid)mdf1(ls, l, mid, ql, qr, y);
if(mid < qr)mdf1(rs, mid + 1, r, ql, qr, y);
upd(x);
}
void mdf2(int x, int l, int r, int ql, int qr, ll y){
if(ql <= l and r <= qr)return (void)(s[x] = (s[x] + y * (r - l + 1)) % p, tg1[x] = (tg1[x] + y) % p);
int mid = l + r >> 1; pd(x, l, r);
if(ql <= mid)mdf2(ls, l, mid, ql, qr, y);
if(mid < qr)mdf2(rs, mid + 1, r, ql, qr, y);
upd(x);
}
ll qry(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return s[x];
int mid = l + r >> 1; ll res = 0; pd(x, l, r);
if(ql <= mid)res = qry(ls, l, mid, ql, qr);
if(mid < qr)res += qry(rs, mid + 1, r, ql, qr);
return res % p;
}
P1253 Problems with Fuso
For this question, note that modification operations have a higher priority than addition operations, and that you need to clear the markers for each modification operation. Then there isDon't be in the leaf node\(\text {pushdown}\)！
void upd(int x){
c[x] = max(c[ls], c[rs]);
}
void build(int x, int l, int r){
tg1[x] = max0810;
if(l == r)return(void)(c[x] = a[l]);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pdtg1(int x){
if(tg1[x] == max0810)return;
tg2[ls] = tg2[rs] = 0;
c[ls] = c[rs] = tg1[ls] = tg1[rs] = tg1[x];
tg1[x] = max0810;
}
void pd(int x){
pdtg1(x);
if(! tg2[x])return;
c[ls] += tg2[x]; c[rs] += tg2[x];
tg2[ls] += tg2[x]; tg2[rs] += tg2[x];
tg2[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int op, ll y){
if(L <= l and r <= R){
if(op ^ 1){
c[x] += y; tg2[x] += y;
}
else{
c[x] = tg1[x] = y;
tg2[x] = 0;
}
return;
}
int mid = l + r >> 1; pd(x);
if(L <= mid)mdfy(ls, l, mid, L, R, op, y);
if(R > mid)mdfy(rs, mid + 1, r, L, R, op, y);
upd(x);
}
ll qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return c[x];
int mid = l + r >> 1; ll res = max0810; pd(x);
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid) res = max(res, qry(rs, mid + 1, r, L, R));
return res;
}
P4513 Little White Walking in the Park See you at 3x experiencethis one(Yes or me)
Line Tree Maintenance Interval Maximum Subsegment Sums for Board Questions with Single Point Modification Support.
Consider the information that needs to be maintained during the process of uploading answers, starting with the interval maximal subsegment and theNo kidding! (gently sarcastic), and then we merge the subintervals with the possibility to start from theMaximum suffix in the left interval plus maximum prefix in the right intervalTransferring the answer, so there are two more things to memorize. Then when updating the prefixes and suffixes it seems that another interval sum needs to be memorized or it can't be transferred (the reader is left to figure that out). Then when you query, you record both of these pieces of information at the same time. A single point of modification will just bisect the change.
struct node{
ll s, lm, rm, sum;
}sgt[N << 2];
void upd(node &x, node y, node z){
= + ;
= max(, max(, + ));
= max(, + ), = max(, + );
}
void bld(int x, int l, int r){
if(l == r)return(void)(sgt[x] = {a[l], a[l], a[l], a[l]});
int mid = l + r >> 1;
bld(ls, l, mid), bld(rs, mid + 1, r);
upd(sgt[x], sgt[ls], sgt[rs]);
}
void mdf(int x, int l, int r, int pos, int y){
if(l == r)return(void)(sgt[x] = {y, y, y, y});
int mid = l + r >> 1;
if(pos <= mid)mdf(ls, l, mid, pos, y);
else mdf(rs, mid + 1, r, pos, y);
upd(sgt[x], sgt[ls], sgt[rs]);
}
node qry(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return sgt[x];
int mid = l + r >> 1; node res, res1, res2; bool o1(false), o2(false);
if(ql <= mid)res1 = qry(ls, l, mid, ql, qr), o1 = true;
if(mid < qr)res2 = qry(rs, mid + 1, r, ql, qr), o2 = true;
if(! o1 or ! o2)res = o1 ? res1 : res2;
else upd(res, res1, res2);
return res;
}
P11071 「QMSOI R1」 Distorted Fate
First dismantle the bit. Observe the equation, there is a press bit or in there, what does that indicate? It shows that if\(a_i\) A one appears in the middle then all the ones that follow have values, so our task is to find the leftmost one in the interval each time then the answer is the length from the first one to the right endpoint.
But seeing the space constraints you realize that this question is a bit abstract, so you're splitting bits and then you're stuck with sharing a line segment tree. Then there's the fact that the line tree maintains whether or not the interval has 0/1, and the possibility of lazy labeling after each isomorphism all three of which can be done with thebool Type of array to maintain.
But that's just offline.Go see for yourself since you won't be online。
struct qarray{
int op, l, r, x; ll ans;
}q[N];
bool b[N], s0[N << 2], s1[N << 2], tg[N << 2];
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
s0[x] = s0[ls] | s0[rs];
s1[x] = s1[ls] | s1[rs];
}
void build(int x, int l, int r){
tg[x] = 0;
if(l == r)return(void)(s0[x] = b[l] ^ 1, s1[x] = b[l]);
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
upd(x);
}
void pd(int x){
if(! tg[x])return ;
tg[ls] ^= 1, tg[rs] ^= 1;
swap(s0[ls], s1[ls]);
swap(s0[rs], s1[rs]);
tg[x] = 0;
}
void mdf(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return(void)(swap(s0[x], s1[x]), tg[x] ^= 1);
int mid = l + r >> 1; pd(x);
if(ql <= mid)mdf(ls, l, mid, ql, qr);
if(mid < qr)mdf(rs, mid + 1, r, ql, qr);
upd(x);
}
int nkp;
bool op;
int fd(int x, int l, int r){
if(l == r)return s1[x] ? l : - 1; pd(x); if(! s1[x])return - 1; int mid = l + r >> 1;
if(s1[ls])return fd(ls, l, mid);
else return fd(rs, mid + 1, r);
}
void qry(int x, int l, int r, int ql, int qr){
if(op)return ;
if(ql <= l and r <= qr){
int res = fd(x, l, r);
if(~ res)nkp = res, op = true;
return;
}
int mid = l + r >> 1; pd(x);
if(ql <= mid)qry(ls, l, mid, ql, qr);
if(op)return ;
if(mid < qr)qry(rs, mid + 1, r, ql, qr);
}
const int p = 1073741824;
signed main(){
n = rd(), m = rd();
for(int i = 1; i <= n; ++i)a[i] = rd();
for(int i = 1; i <= m; ++i){
int x = rd(), l = rd(), r = rd(), y;
q[i] = {x, l, r};
if(x == 1)q[i].x = rd();
}
for(int bit = 0; bit < 31; ++bit){
for(int i = 1; i <= n; ++i)b[i] = a[i] >> bit & 1;
build(1, 1, n);
for(int i = 1; i <= m; ++i)if(q[i].op == 1){
int x = q[i].x >> bit & 1;
if(! x)continue; mdf(1, 1, n, q[i].l, q[i].r);
}else{
op = false, nkp = q[i].r + 1; qry(1, 1, n, q[i].l, q[i].r);
q[i].ans += 1ll * (q[i].r - nkp + 1) * (1ll << bit) % p;
q[i].ans %= p;
}
}
for(int i = 1; i <= m; ++i)if(q[i].op ^ 1)printf("%lld\n", q[i].ans);
return 0;
}
Line Tree Extension 1 (Persistable)
Persistable is really just adding a feature that allows you to access the historical version, like if I ask for the answer after a certain previous revision you can have the same complexity as a normal line tree\(O(\log n)\) Answer.
Consider exactly how this will be implemented. In fact, for each modification operation, we will only modify the\(O(\log n)\) We can then pull out the chain of these points, and for each operation we can "open" a new segment tree, like this.
Let's think of each operation as a tree root, and go down the original tree when modifying it, and if a point isn't modified, it's inherited directly into the current tree, otherwise a new node is opened. Then everything else goes as it should, and the various line segment trees that you normally apply to this should work fine.
And then we have to talk about something very important.
Persistent Weighted Line Tree (Chairman's Tree)
Yes, if we make the weighted line tree persistent, it becomes the proverbial Chairman's Tree. This thing is capable of querying the static intervals of the first\(k\) Small. As for the dynamic interval No.\(k\) Smaller, can't we just put a tree array on top of it?
Let's start with the static. We think of inputting each number as a single operation, and each operation as modifying a point in the value field. Then the query can be viewed as a prefix sum. When going through the tree, for finding the current interval\([l,r]\) The first value in the value field of the\(k\) large, I bisect the line tree normally, but bisecting two line trees at the same time for a\(mid\), the first half of the value range is in\([l,r]\) number of neutralsequivalence\([1,r]\) The number of neutrals minus the number of\([1,l-1]\) number of neutrals. Then you can just do it.
P3834 Board as well asP1533 Poor dogDouble experience (true just copy it directly)
The code is as follows:
int n, m, a[N], b[N], tt;
int rt[N << 5], c[N << 5], nd, ls[N << 5], rs[N << 5];
void upd(int &x, int y, int l, int r, int p){
x = ++nd; c[x] = c[y] + 1;
if(l == r)return; int mid = l + r >> 1;
if(p <= mid)rs[x] = rs[y], upd(ls[x], ls[y], l, mid, p);
else ls[x] = ls[y], upd(rs[x], rs[y], mid + 1, r, p);
}
int qry(int x, int y, int l, int r, int k){
if(l == r)return l; int mid = l + r >> 1, res = c[ls[x]] - c[ls[y]];
if(res >= k)return qry(ls[x], ls[y], l, mid, k);
return qry(rs[x], rs[y], mid + 1, r, k - res);
}
signed main(){
n = rd(), m = rd();
for(int i = 1; i <= n; ++i)a[i] = b[i] = rd();
sort(b + 1, b + 1 + n);
tt = unique(b + 1, b + 1 + n) - b - 1;
for(int i = 1; i <= n; ++i)a[i] = lower_bound(b + 1, b + 1 + tt, a[i]) - b, upd(rt[i], rt[i - 1], 1, tt, a[i]);
for(int i = 1; i <= m; ++i){
int l = rd(), r = rd(), k = rd();
printf("%d\n", b[qry(rt[r], rt[l - 1], 1, tt, k)]);
}
return 0;
}
P2617 Dynamic Rankings
Then consider what to do about dynamic intervals.
We can give the chairman of the tree set a tree array, each violent modification after the maintenance of the tree array, note that the tree array record is actually only the root of each chairman of the tree, so run the tree array at each point to be modified in the corresponding chairman of the tree. Query can be analogous to the above, the above we recorded two tree roots, now we can put the tree array on some of the tree roots related to open two arrays to remember, each time the two points on the answer to all the trees cumulative, the other parts of the above is similar to no longer repeat.
The code is as follows:
namespace SGT{
int nd, rt[N << 9], ls[N << 9], rs[N << 9], c[N << 9];
void gotols(){
for(int i = 1; i <= c1; ++i)q1[i] = ls[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = ls[q2[i]];
}
void gotors(){
for(int i = 1; i <= c1; ++i)q1[i] = rs[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = rs[q2[i]];
}
void upd(int &x, int l, int r, int p, int y){
if(! x)x = ++nd; c[x] += y;
if(l == r)return; int mid = l + r >> 1;
if(p <= mid)upd(ls[x], l, mid, p, y);
else upd(rs[x], mid + 1, r, p, y);
}
int qryk(int l, int r, int k){
if(l == r)return l; int mid = l + r >> 1, res = 0;
for(int i = 1; i <= c1; ++i)res -= c[ls[q1[i]]];
for(int i = 1; i <= c2; ++i)res += c[ls[q2[i]]];
if(res >= k)return gotols(), qryk(l, mid, k);
return gotors(), qryk(mid + 1, r, k - res);
}
int qryrk(int l, int r, int k){
if(l == r)return 0; int mid = l + r >> 1, res = 0;
if(k <= mid)return gotols(), qryrk(l, mid, k);
for(int i = 1; i <= c1; ++i)res -= c[ls[q1[i]]];
for(int i = 1; i <= c2; ++i)res += c[ls[q2[i]]];
return gotors(), res + qryrk(mid + 1, r, k);
}
}
using namespace SGT;
namespace BIT{
int lb(int x){return x & - x;}
void get(int l, int r){
c1 = c2 = 0;
for(int i = l - 1; i; i -= lb(i))q1[++c1] = rt[i];
for(int i = r; i; i -= lb(i))q2[++c2] = rt[i];
}
void mdf(int p, int y){
int x = lower_bound(b + 1, b + 1 + tt, a[p]) - b;
for(; p <= n; p += lb(p))upd(rt[p], 1, tt, x, y);
}
int kth(int l, int r, int k){get(l, r); return qryk(1, tt, k);}
int rk(int l, int r, int k){int kk = lower_bound(b + 1, b + 1 + tt, k) - b; get(l, r); return qryrk(1, tt, kk) + 1;}
}
P2839 [National training team] middle
First analyze the nature of the question and think about what characterizes our answer. Because we are looking for the largest median, shouldn't we be able to bisect it. Assuming that the current bisection of a\(mid\)The first is to assign a value greater than or equal to it to one, otherwise zero, and then see whether the sub-segment sum is greater than or equal to zero can be judged. For this question, that is, the middle of the determination of the part of the value domain can be used to maintain the line tree, the left and right sides and then open a line tree to maintain the prefix and suffix of the largest sub-segment and on the line.
And then as far as the code is concerned, it's what I put in my ancient time writingI'm having a hard time watching it myself.Mystery Code.
#include<bits/stdc++.h>
#define s(x) tr[x].sum
#define ls(x) tr[x].lson
#define rs(x) tr[x].rson
#define lm(x) tr[x].lmx
#define rm(x) tr[x].rmx
#define lc(x) tr[x].ncl
#define rc(x) tr[x].ncr
using namespace std;
const int N = 2e4 + 10;
int n, m, a[N], num[N], cnt, rt[N], idq, x1, x2, x3, x4;
int L(int x){return lower_bound(num + 1, num + cnt + 1, x) - num;}
struct tree
{
int sum, lmx, rmx;
int lson, rson;
bool ncl, ncr;
}tr[N * 40];
vector < int > c[N];
void upd(int x)
{
s(x) = s(ls(x)) + s(rs(x));
lm(x) = max(lm(ls(x)), s(ls(x)) + lm(rs(x)));
rm(x) = max(rm(rs(x)), s(rs(x)) + rm(ls(x)));
}
int build(int l, int r)
{
int x = ++idq;
if(l == r)
{
if(L(a[l]) < 2)s(x) = lm(x) = rm(x) = - 1;
else s(x) = lm(x) = rm(x) = 1;
return x;
}
int mid = l + r >> 1; lc(x) = rc(x) = 1;
ls(x) = build(l, mid); rs(x) = build(mid + 1, r);
upd(x); return x;
}
int modify(int x, int y, int l, int r, int to, int val, bool cc)
{
if(!cc)x = ++idq;
if(l == r)
{
s(x) = lm(x) = rm(x) = val;
return x;
}
int mid = l + r >> 1;
if(to <= mid)
{
if(!rc(x)) rs(x) = rs(y);
if(!lc(x))lc(x) = 1, ls(x) = modify(x, ls(y), l, mid, to, val, 0);
else ls(x) = modify(ls(x), ls(y), l, mid, to, val, 1);
}
else
{
if(!lc(x)) ls(x) = ls(y);
if(!rc(x))rc(x) = 1, rs(x) = modify(x, rs(y), mid + 1, r, to, val, 0);
else rs(x) = modify(rs(x), rs(y), mid + 1, r, to, val, 1);
}
upd(x); return x;
}
int query(int x, int l, int r, int L, int R)
{
if(L <= l and r <= R)return s(x);
int mid = l + r >> 1; int ret = 0;
if(L <= mid)ret += query(ls(x), l, mid, L, R);
if(mid < R)ret += query(rs(x), mid + 1, r, L, R);
return ret;
}
tree query1(int x, int l, int r, int L, int R)
{
if(L <= l and r <= R)return tr[x];
int mid = l + r >> 1;
if(L <= mid and mid < R)
{
tree ret;
tree le = query1(ls(x), l, mid, L, R);
tree ri = query1(rs(x), mid + 1, r, L, R);
= + ;
= max(, + );
return ret;
}
else if(L <= mid)return query1(ls(x), l, mid, L, R);
else return query1(rs(x), mid + 1, r, L, R);
}
tree query2(int x, int l, int r, int L, int R)
{
if(L <= l and r <= R)return tr[x];
int mid = l + r >> 1;
if(L <= mid and mid < R)
{
tree ret;
tree le = query2(ls(x), l, mid, L, R);
tree ri = query2(rs(x), mid + 1, r, L, R);
= + ;
= max(, + );
return ret;
}
else if(L <= mid)return query2(ls(x), l, mid, L, R);
else return query2(rs(x), mid + 1, r, L, R);
}
bool check(int val)
{
int sz = 0;
if(x2 + 2 <= x3) sz = query(rt[val], 1, n, x2 + 1, x3 - 1);
int sr = query1(rt[val], 1, n, x3, x4).lmx;
int sl = query2(rt[val], 1, n, x1, x2).rmx;
return (sl + sz + sr) >= 0;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)scanf("%d", &a[i]), num[++cnt] = a[i];
sort(num + 1, num + cnt + 1);
cnt = unique(num + 1, num + cnt + 1) - num - 1;
for(int i = 1; i <= n; i++)c[L(a[i])].push_back(i);
rt[1] = build(1,n);
for(int i = 2; i <= cnt; i++)for(int j = 0; j < c[i - 1].size(); j++)
{
int go = c[i - 1][j];
rt[i] = modify(rt[i], rt[i - 1], 1, n, go, - 1, rt[i] > 0);
}
scanf("%d", &m);
int las = 0;
int d[6];
while(m--)
{
scanf("%d %d %d %d", &x1, &x2, &x3, &x4);
d[1] = (x1 + las) % n;
d[2] = (x2 + las) % n;
d[3] = (x3 + las) % n;
d[4] = (x4 + las) % n;
sort(d + 1, d + 5);
x1 = d[1] + 1, x2 = d[2] + 1, x3 = d[3] + 1, x4 = d[4] + 1;
int l = 1, r = cnt;
int ans = 0;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid))ans = mid, l = mid + 1;
else r = mid - 1;
}
las = num[ans];
printf("%d\n", las);
}
return 0;
}
P4137 Rmq Problem / mex
Set of questions. Consider each time we record\(val\) Last Existing Location, Query Interval\([l,r]\) precisely\(rt_r\) sub-tree to find the sub-tree that satisfies the requirement that the occurrence time is less than\(l\) minimum\(val\). It is sufficient to maintain the minimum value with a chairman tree.
void upd(int &x, int y, int l, int r, int p, int val){
if(! x)x = ++tot; if(l == r)return(void)(ans[x] = val); int mid = l + r >> 1;
if(p <= mid)rs[x] = rs[y], upd(ls[x], ls[y], l, mid, p, val);
else ls[x] = ls[y], upd(rs[x], rs[y], mid + 1, r, p, val);
ans[x] = min(ans[ls[x]], ans[rs[x]]);
}
int qry(int x, int l, int r, int lim){
if(l == r)return l; int mid = l + r >> 1;
if(ans[ls[x]] < lim)return qry(ls[x], l, mid, lim);
else return qry(rs[x], mid + 1, r, lim);
}
signed main(){
// fileio(fil);
n = rd() + 1, m = rd();
for(int i = 1, x; i < n; ++i){
x = rd() + 1; if(x > n)rt[i] = rt[i - 1];
else upd(rt[i], rt[i - 1], 1, n, x, i);
}
for(int i = 1; i <= m; ++i){
int l = rd(), r = rd();
printf("%d\n", qry(rt[r], 1, n, l) - 1);
}
return 0;
}
Line Tree Extension 2 (Line Tree Merging)
Note that the merge should be done withDynamic open-point line segment treeOtherwise the complexity would be\(O(n\log^2n)\) s, since the tree of line segments has\(O(n\log n)\) nodes, the merge is again\(O(\log n)\) The.
How to merge? We still walk up the tree, and if there is a node (maybe one or two) that is empty when we get to a point, we can just return to another node, otherwise we recursively go down the tree and just merge back when we get to the leaf. But at first glance doesn't this look like an explosion? So next we need tospouting gibberishBreak down the complexity.
It is easy to find out: in the process of merging two trees walking to the empty nodes returns, which is equivalent to walking one point and deleting some points, so the total complexity will not exceed the total number of points that is\(O(n\log n)\)。
Before I talk about the problem, let's talk about my understanding of merging line segment trees. The reason why we need to merge line segment trees in the first place is that for some problems we need to merge information that is\(O(n)\) level, and for such formulas we definitely need an\(O(\log)\) The way to optimize. Then it is how to understand the merging process, because if you really open a line tree for each point that surely explosion has nothing to say. In fact, we are each point corresponds to a section of the interval, or subscripts or value domain, and then for each point of the line tree dynamics of the point, and finally the merger process is not just add and subtract, but according to your formula to restore the whole process, perhaps you do not quite understand, but when you look at the back of a certain question after you will suddenly realize.
Then look at a board.
P4556 [Vani has a date] Tail of the Rainy Day / [Template] Line Tree Merge
Observing that it is modified on the tree, one can associate it with a certain classical routine that transforms a path on the tree into a difference. Specifically, for a path\((u,v)\)set up\(t=lca(u,v)\)Then I can put in a list of the most important things to do with\((u,v)\) The operation is viewed as for\((root,u)\) cap (a poem)\((root,v)\) The operation of the\((root,t)\) cap (a poem)\((root,fa_t)\) the inverse operation. Then consider opening a line segment tree for each point. This question could be done by subscripting the line segment tree with color, and then it would seem to be a single point modification (direct line segment tree bisection) plus a line segment tree merge.
Then pay a little attention to the fact that you need to run through the dfs procedure when merging on the tree, and then merge when you return recursively.
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1, sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
int lca(int u, int v){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
u = fa[tp[u]];
}
return dep[u] < dep[v] ? u : v;
}
void upd(int x){
if(s[ls[x]] > s[rs[x]] or (s[ls[x]] == s[rs[x]] and col[ls[x]] < col[rs[x]]))return(void)(s[x] = s[ls[x]], col[x] = col[ls[x]]);
s[x] = s[rs[x]], col[x] = col[rs[x]];
}
void md(int &p, int l, int r, int c, int y){
if(! p)p = ++tot;
if(l == r)return(void)(s[p] += y, col[p] = c);
int mid = l + r >> 1;
if(c <= mid)md(ls[p], l, mid, c, y);
else md(rs[p], mid + 1, r, c, y);
upd(p);
}
int merge(int a, int b, int l, int r){
if(! a or ! b)return a | b;
if(l == r)return s[a] += s[b], a;
int mid = l + r >> 1;
ls[a] = merge(ls[a], ls[b], l, mid);
rs[a] = merge(rs[a], rs[b], mid + 1, r);
upd(a); return a;
}
void dfs(int u){
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u])continue;
dfs(v); rt[u] = merge(rt[u], rt[v], 1, 100000);
}
if(s[rt[u]])ans[u] = col[rt[u]];
}
signed main(){
n = rd(), q = rd();
for(int i = 1; i < n; ++i){
int u = rd(), v = rd();
add(u, v); add(v, u);
}
dfs1(1, 0); dfs2(1, 1);
for(int i = 1; i <= q; ++i){
int u = rd(), v = rd(), w = rd();
md(rt[u], 1, 100000, w, 1); md(rt[v], 1, 100000, w, 1);
int f = lca(u, v);
md(rt[f], 1, 100000, w, - 1); md(rt[fa[f]], 1, 100000, w, - 1);
}
dfs(1);
for(int i = 1; i <= n; ++i)printf("%d\n", ans[i]);
return 0;
}
P3224 [HNOI2012] No Country Forever
How does it feel a little too board?
For finding the first\(k\) For big problems we use a value field line segment tree and then consider how do we solve for connectivity? Then you'll find direct concatenation set maintenance, and then the concatenation set is the daisy chart, which opens a line segment tree for the center of each flower, and then just merges normally.
int fd(int x){
return x == f[x] ? x : f[x] = fd(f[x]);
}
void upd(int x){
s[x] = s[ls[x]] + s[rs[x]];
}
void md(int &p, int l, int r, int y){
if(! p)p = ++cnt;
if(l == r)return(void)(++s[p]);
int mid = l + r >> 1;
if(y <= mid)md(ls[p], l, mid, y);
else md(rs[p], mid + 1, r, y);
upd(p);
}
int merge(int a, int b, int l, int r){
if(! a or ! b)return a | b;
if(l == r)return s[a] += s[b], a;
int mid = l + r >> 1;
ls[a] = merge(ls[a], ls[b], l, mid);
rs[a] = merge(rs[a], rs[b], mid + 1, r);
upd(a); return a;
}
int qry(int p, int l, int r, int y){
if(l == r)return l;
int mid = l + r >> 1, ans;
if(s[ls[p]] >= y)ans = qry(ls[p], l, mid, y);
else ans = qry(rs[p], mid + 1, r, y - s[ls[p]]);
return ans;
}
void sol1(){
int x = rd(), y = rd();
x = fd(x), y = fd(y);
if(x == y)return;
f[y] = x; rt[x] = merge(rt[x], rt[y], 1, 100000);
}
signed main(){
n = rd(), m = rd();
for(int i = 1, x; i <= n; ++i)md(rt[i], 1, 100000, x = rd()), f[i] = i, pos[x] = i;
for(int i = 1; i <= m; ++i)sol1();
q = rd();
for(int i = 1; i <= q; ++i){
char c; cin >> c;
if(c == 'B')sol1();
else{
int x = rd(), y = rd(); x = fd(x);
if(s[rt[x]] < y){puts("-1"); continue;}
printf("%d\n", pos[qry(rt[x], 1, 100000, y)]);
}
}
return 0;
}
Is that too easy? Then let's have a little bit of a difficult one.
P5298 [PKUWC2018] Minimax
For this question we can easily think of a violence dp, letting\(f_{u,i}\) indicate\(u\) The node is the first\(i\) The probability of a larger number. And then the answer is:
Then to start the transfer, we make the current point\(u\) His left son's name is\(l\)The right son is called\(r\), and the transfer formula is called out:
I hope there's no clerical error.
Then you realize that every time you need to take a piece of prefix out and transfer it, can you optimize it? Yet it can indeed be. Consider line tree maintenance, where the subscript is the rank (the second dimension of the dp). Now you take each\(f_i\) are viewed as pointwise weights on a binary tree, which can then be merged However, the
Consider that the merger in this problem is not a mere addition or subtraction; in the transfer equation we introduced above\(f_i\) is with coefficients, so we also need to memorize the coefficients when combining, so how do we find the coefficients?
Consider splitting up the above equation, that is, for a point in the line tree\(i\), which it coefficients is:
In human terms it is the probability that the point on the left (subscript) is smaller than it multiplied by the corresponding node\(p\) Plus the right side. So just follow the implementation above.
summary of the topic
In fact, the essence of merging line tree is to optimize the state transfer. For the order of the merger need to pay attention to the specific choice of tools used with the line tree, and then for the merger of the formula is actually the transfer of the reproduction of the formula, the specific point is thatSplitting and then multiplying the distributive law to combine like terms。
Expanding on the general question, we can start by considering native's idea of writing slightly more violent ways of transferring and maintaining things, and then looking at what properties can be used to make these things have some elegant properties, like additivity, subtractability, monotonicity, or something like that, and then finally thinking about how to set up a line tree to look elegant.
coding
const db eps = 1e-8;
const ll inf = 1e18;
const int N = 3e5 + 5, p = 998244353;
ll qmi(ll x, ll y){
ll res = 1ll;
for(; y; y >>= 1, x = x * x % p)if(y & 1)res = res * x % p;
return res;
}
const ll ii = qmi(10000, p - 2);
int n, b[N], nd, m;
int rt[N << 5], ls[N << 5], rs[N << 5];
ll s[N << 5], tg[N << 5], f[N], a[N];
int fa[N], c[N], ch[N][2];
inline int jia(int x, int y){return x - p + y >= 0 ? x - p + y : x + y;}
void upd(int x){
s[x] = jia(s[ls[x]], s[rs[x]]);
}
void updd(int x, ll y){
if(! x)return;
s[x] = s[x] * y % p;
tg[x] = tg[x] * y % p;
}
void pd(int x){
if(tg[x] == 1)return;
updd(ls[x], tg[x]), updd(rs[x], tg[x]);
return (void)(tg[x] = 1);
}
void addin(int &x, int l, int r, int pos){
if(! x)tg[x = ++nd] = 1;
if(l == r)return(void)(s[x] = 1);
int mid = l + r >> 1; pd(x);
if(pos <= mid)addin(ls[x], l, mid, pos);
else addin(rs[x], mid + 1, r, pos);
upd(x);
}
int merge(int x, int y, int l, int r, ll sx, ll sy, ll pp){
if(! x or ! y)return updd(x | y, (x ? sx : sy)), x | y;
int mid = l + r >> 1; pd(x), pd(y);
ll lsl = s[ls[x]], rsl = s[rs[x]], lsr = s[ls[y]], rsr = s[rs[y]];
ls[x] = merge(ls[x], ls[y], l, mid, jia(sx, rsr * (p + 1 - pp) % p), jia(sy, rsl * (p + 1 - pp) % p), pp);
rs[x] = merge(rs[x], rs[y], mid + 1, r, jia(sx, lsr * pp % p), jia(sy, lsl * pp % p), pp);
return upd(x), x;
}
void dfs(int u){
if(! c[u])addin(rt[u], 1, m, a[u]);
if(c[u] == 1)dfs(ch[u][0]), rt[u] = rt[ch[u][0]];
if(c[u] == 2)dfs(ch[u][0]), dfs(ch[u][1]), rt[u] = merge(rt[ch[u][0]], rt[ch[u][1]], 1, m, 0, 0, a[u]);
}
void getans(int x, int l, int r){
if(! x)return;
if(l == r)return(void)(f[l] = s[x]);
int mid = l + r >> 1; pd(x);
getans(ls[x], l, mid); getans(rs[x], mid + 1, r);
}
int main(){
rd(n);
for(int i = 1; i <= n; ++i)rd(fa[i]), fa[i] ? ch[fa[i]][c[fa[i]]++] = i : 0;
for(int i = 1; i <= n; ++i){
rd(a[i]);
if(c[i])a[i] = a[i] * ii % p;
else b[++m] = a[i];
}
sort(b + 1, b + 1 + m);
for(int i = 1; i <= n; ++i)if(! c[i])a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b;
dfs(1); getans(rt[1], 1, m); ll ans = 0;
for(int i = 1; i <= m; ++i)ans = jia(ans, 1ll * i * b[i] % p * f[i] % p * f[i] % p);
wt(ans);
return 0;
}
(Why is there no line-tree split? BecauseI won't.It's not very common, so I'll put it away for now.)
Extension of Line Tree 3 (Li Chao Line Tree)
As a brief introduction, the Lee Ultra Line Segment Tree maintains a number of line segments, and it allows for a quick lookup of the number of the line segment with the largest/smallest vertical coordinate at the location, as well as the value. Consider that this kind of thing would be good to go to solve something that needs to beFinding the Most Valuable Transfer State from an IntervalThe question.
Then talk about the implementation and application.
The nodes of the Lee Hyperlinear Tree are maintained on the\(mid\) The line segment with the largest longitudinal coordinate at the end of the tree, so it's pretty violent when it comes to actually maintaining it. Find its range directly in the tree and then just violently compare the line segments one at a time and you're done. Analyzing the complexity, the lookup is a\(\log\), and then the violent update because the two primary functions have at most one intersection, so it recursively recurses a subinterval afterward, and the complexity is also one\(\log\)So that's two in total.\(\log\)。
The query just walks from the root to the corresponding leaf node, noting the maximum value along the way as it goes, and you're done.
bamboo or birch for corporal punishmentand hisdouble experience
const int N = 1e5 + 5, mod1 = 39989, mod2 = 1e9 + 1;
const ll INF = 1e18;
int n;
lb k[N], b[N];
int sgt[N << 2];
#define ls x << 1
#define rs x << 1 | 1
lb calc(int x, int pos){
return k[x] * pos + b[x];
}
bool eq(lb a, lb b){
lb eps = 1e-10;
if(a - b < eps and b - a < eps)return true;
return false;
}
bool cmp(int x1, int x2, int pos){
lb a = calc(x1, pos), b = calc(x2, pos);
return a > b || (a == b and x1 < x2);
}
void _upd(int tmp, int x, int l, int r){
int mid = l + r >> 1;
if(cmp(tmp, sgt[x], mid))swap(tmp, sgt[x]);
if(cmp(tmp, sgt[x], l))_upd(tmp, ls, l, mid);
if(cmp(tmp, sgt[x], r))_upd(tmp, rs, mid + 1, r);
}
void upd(int x, int l, int r, int L, int R, int tmp){
if(L <= l and r <= R)return _upd(tmp, x, l, r);
int mid = l + r >> 1;
if(L <= mid)upd(ls, l, mid, L, R, tmp);
if(R > mid)upd(rs, mid + 1, r, L, R, tmp);
}
int qry(int x, int l, int r, int pos){
int mid = l + r >> 1, res = sgt[x];
if(l == r)return res;
int tmp = pos <= mid ? qry(ls, l, mid, pos) : qry(rs, mid + 1, r, pos);
if(cmp(tmp, res, pos))swap(res, tmp);
return res;
}
signed main(){
n = rd();
b[0] = - INF;
int ans = 0, cnt = 0;
for(int i = 1; i <= n; ++i){
int op = rd();
if(op == 0){
int pos = (rd() + ans + mod1 - 1) % mod1 + 1;
printf("%d\n", ans = qry(1, 1, mod1, pos));
}
else{
int x1 = rd(), y1 = rd(), x2 = rd(), y2 = rd();
x1 = (x1 + ans - 1) % mod1 + 1;
y1 = (y1 + ans - 1) % mod2 + 1;
x2 = (x2 + ans - 1) % mod1 + 1;
y2 = (y2 + ans - 1) % mod2 + 1;
if(x1 > x2)swap(x1, x2), swap(y1, y2);
if(x1 == x2)k[++cnt] = 0, b[cnt] = max(y1, y2);
else{
k[++cnt] = (lb)(y1 - y2) / (x1 - x2);
b[cnt] = y1 - k[cnt] * x1;
}
upd(1, 1, mod1, x1, x2, cnt);
}
}
return 0;
}
Then talk about some applications (?)
In fact, the Li Chao line segment treemost of allThe use of dp is still tested in conjunction with slope optimization dp, and I was going to put it later in conjunction with dp, but thought better of it. But I've written very few questions in this section, so I'll talk a little bit about the secondary ones.
P3081 [USACO13MAR] Hill Walk G
We started with\((0,0)\) Start walking. If we just build Li Hyperlinear Tree then we have a problem when we want to take the line segments of the following part, so we need something that supports deletion to maintain it. So consider a balanced tree.
Then when we walk we are sorting in horizontal coordinates, so now we just use to consider vertical coordinates. At the end of each walk we need to see who is one level below the current segment in the feasible interval. Then it came up with the idea of throwing all the line segments into a balanced tree and making those line segments sorted from highest to lowest by some sort of sorting party.
So how do you determine the height of two line segments? Let's analyze it through the following chart.
If I were to compare the two line segments above, I would first go to the position of their right endpoints. Obviously the latter is further to the right, and then we connect their right endpoints (as shown in the red line). If the former is higher (as shown), thenThe slope of the red line will be less than the slope of the line segment behind it, otherwise it would be the case in the bottom half of the picture. So when we compare the priority between line segments we can compare the right endpoints before comparing the slopes.
bool operator <(line x, line y){
if( < )return 1ll * ( - ) * ( - ) < 1ll * ( - ) * ( - );
return 1ll * ( - ) * ( - ) > 1ll * ( - ) * ( - );
}
Note that if you use division directly the accuracy may blow up.
Then it sweeps from left to right, adding line segments to the balance tree if they should be added and deleting them if they should be deleted. If the deleted segment is in the current interval, it looks for a segment one level below it in the balance tree and updates the answer. The actual implementation can be done withset Instead of balancing the tree.
int main(){
rd(n);
for(int i = 1; i <= n; ++i)rd(l[i].a, l[i].b, l[i].c, l[i].d), p[i - 1 << 1 | 1] = {l[i].a, l[i].b, i}, p[i << 1] = {l[i].c, l[i].d, i}, l[i].id = i;
(l[1]); sort(p + 1, p + 1 + (n << 1));
for(int i = 2; i <= (n << 1); ++i)
if(p[i].x == l[p[i].id].a)(l[p[i].id]);
else if(p[i].id == cur){
set < line > :: iterator it = (l[p[i].id]);
if(it == ())break;
++ans; it--;
cur = it -> id;
}
else (l[p[i].id]);
wt(ans);
return 0;
}
There was a question but I put it in the tree dissection set of line segment trees.
There was another question but I put it back into dp optimization.
So for various reasons, this is the end of the Li Chao Line Segment Tree! But I can guarantee that you'll find the Li Chao Line Segment Tree in what follows.
Line Tree Extension 4 (Scanning Lines)
Here only talk about the narrow scanning line is also known as the sweeping area and, as for the broad sweeping line and so on after the time I will write a separate blog to explain in detail.
Just a quick note on sweeping areas and. Using the example of sweeping from top to bottom, we can break the graph into a number ofLine segments parallel to the horizontal axis representing plus one minus one. Each time we pass through a line segment, the cross-sectional length of this odd-shaped graph changes, and we can maintain this change each time and count the area corresponding to the last cross-sectional length. Then for passing through line segments, we can think of it as adding or subtracting intervals, and the query is asking for the number of non-zeros in the interval.
bamboo or birch for corporal punishment
int n, cnt[N << 2], top;
ll f[N << 2], y[N << 2], ans;
struct node{
ll x1, y1, y2;
int op;
bool operator < (const node &rhs)const {
return x1 < rhs.x1;
}
}a[N << 2];
#define ls x << 1
#define rs x << 1 | 1
void upd(int x, int l, int r){
if(cnt[x])return (void)(f[x] = y[r] - y[l - 1]);
f[x] = f[ls] + f[rs];
}
void modify(int x, int l, int r, int L, int R, int op){
if(L <= l and r <= R){cnt[x] += op; upd(x, l, r); return;}
int mid = l + r >> 1;
if(L <= mid)modify(ls, l, mid, L, R, op);
if(R > mid)modify(rs, mid + 1, r, L, R, op);
upd(x, l, r);
}
signed main(){
//freopen(, stdin);
//freopen(, stdout);
n = rd();
for(int i = 1; i <= n; ++i){
ll x1 = rd(), y1 = rd(), x2 = rd(), y2 = rd();
a[++top] = {x1, y1, y2, 1}; y[top] = y1;
a[++top] = {x2, y1, y2, - 1}; y[top] = y2;
}
sort(y + 1, y + 1 + top);
sort(a + 1, a + 1 + top);
n = unique(y + 1, y + 1 + top) - y - 1;
for(int i = 1; i <= top; ++i){
ans += f[1] * (a[i].x1 - a[i - 1].x1);
int l = lower_bound(y + 1, y + 1 + n, a[i].y1) - y;
int r = lower_bound(y + 1, y + 1 + n, a[i].y2) - y;
modify(1, 1, n, l + 1, r, a[i].op);
}
printf("%lld", ans);
return 0;
}
Line Tree Extension 5 (Tree over Tree)
When maintaining high-dimensional information, it is clear that a simple line tree is not up to the task.Simple and well-written cdq instead of making the sameTree over tree.
Tree over tree is usually only two layers, three layers is really impossible to write. For a two-layer tree, the inner layer is usually a very normal tree, it will maintain the information normally, and then the outer layer of the tree has a little bit of change, because the outer layer of the tree is not to maintain some information, but some trees, so in order to facilitate the maintenance of the root of the tree information. And then talk a little bit about modifications.
There's not much to talk about, really. It's just an outer run-through.Modify whatever points are relevant!Just go to the inner run and recursively update upwards if you need to make changes.
The query is queried as normal, and when the interval is found it changes from returning the answer directly to querying the inner layer.
There's a question that's a little easier than the board that's in the chair tree, so let's just go straight to the board here. And then no amount of lectures on this kind of stuff is better than looking at someone else's well-written code and thinking it through yourself.
bamboo or birch for corporal punishment
namespace SGT{
int nd, rt[N << 9], ls[N << 9], rs[N << 9], c[N << 9];
void gotols(){
for(int i = 1; i <= c1; ++i)q1[i] = ls[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = ls[q2[i]];
}
void gotors(){
for(int i = 1; i <= c1; ++i)q1[i] = rs[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = rs[q2[i]];
}
void upd(int &x, int l, int r, int p, int y){
if(! x)x = ++nd; c[x] += y;
if(l == r)return; int mid = l + r >> 1;
if(p <= mid)upd(ls[x], l, mid, p, y);
else upd(rs[x], mid + 1, r, p, y);
}
int qryk(int l, int r, int k){
if(l == r)return l; int mid = l + r >> 1, res = 0;
for(int i = 1; i <= c1; ++i)res -= c[ls[q1[i]]];
for(int i = 1; i <= c2; ++i)res += c[ls[q2[i]]];
if(res >= k)return gotols(), qryk(l, mid, k);
return gotors(), qryk(mid + 1, r, k - res);
}
int qryrk(int l, int r, int k){
if(l == r)return 0; int mid = l + r >> 1, res = 0;
if(k <= mid)return gotols(), qryrk(l, mid, k);
for(int i = 1; i <= c1; ++i)res -= c[ls[q1[i]]];
for(int i = 1; i <= c2; ++i)res += c[ls[q2[i]]];
return gotors(), res + qryrk(mid + 1, r, k);
}
}
using namespace SGT;
namespace BIT{
int lb(int x){return x & - x;}
void get(int l, int r){
c1 = c2 = 0;
for(int i = l - 1; i; i -= lb(i))q1[++c1] = rt[i];
for(int i = r; i; i -= lb(i))q2[++c2] = rt[i];
}
void mdf(int p, int y){
int x = lower_bound(b + 1, b + 1 + tt, a[p]) - b;
for(; p <= n; p += lb(p))upd(rt[p], 1, tt, x, y);
}
int kth(int l, int r, int k){get(l, r); return qryk(1, tt, k);}
int rk(int l, int r, int k){int kk = lower_bound(b + 1, b + 1 + tt, k) - b; get(l, r); return qryrk(1, tt, kk) + 1;}
int pre(int l, int r, int k){
k = rk(l, r, k) - 1; return k > 0 ? b[kth(l, r, k)] : - INF;
}
int suf(int l, int r, int k){
k = rk(l, r, k + 1); return k < r - l + 2 ? b[kth(l, r, k)] : INF;
}
}
P4175 [CTSC2008] Network Administration
While this looks very tree-over-tree+tree-anatomy it's actually possible to merge the answer differentials a bit more to throw out a\(\log\), which maintains the prefixed chairperson tree in this way, and the query just looks up the four trees, which ends up being the\(O(n\log^2n)\). But I didn't care much at all after reading the questions and seeing the three\(\log\) If you can get through it, you'll be able to write about the tree and get through it.
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1, sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to; if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int tp){
top[u] = tp; dfn[u] = ++tim, rk[tim] = u;
if(son[u])dfs2(son[u], tp);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v ^ fa[u] and v ^ son[u])dfs2(v, v);
}
}
void gotols(){
for(int i = 1; i <= c1; ++i)q1[i] = ls[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = ls[q2[i]];
}
void gotors(){
for(int i = 1; i <= c1; ++i)q1[i] = rs[q1[i]];
for(int i = 1; i <= c2; ++i)q2[i] = rs[q2[i]];
}
void upd(int &x, int l, int r, int pos, int y){
if(! x)x = ++nd; s[x] += y;
if(l == r)return; int mid = l + r >> 1;
if(pos <= mid)upd(ls[x], l, mid, pos, y);
else upd(rs[x], mid + 1, r, pos, y);
}
int getsum(){
int sum = 0;
for(int i = 1; i <= c1; ++i)sum -= s[q1[i]];
for(int i = 1; i <= c2; ++i)sum += s[q2[i]];
return sum;
}
int qryk(int l, int r, int k){
if(l == r)return getsum() >= k ? l : 0; int mid = l + r >> 1, sum = 0;
for(int i = 1; i <= c1; ++i)sum -= s[rs[q1[i]]];
for(int i = 1; i <= c2; ++i)sum += s[rs[q2[i]]];
if(k <= sum)return gotors(), qryk(mid + 1, r, k);
return gotols(), qryk(l, mid, k - sum);
}
void get(int l, int r){
for(int i = l - 1; i; i -= i & - i)q1[++c1] = rt[i];
for(int i = r; i; i -= i & - i)q2[++c2] = rt[i];
}
void mdf(int pos, int y){
int x = lower_bound(b + 1, b + 1 + m, a[rk[pos]]) - b;
for(; pos <= n; pos += pos & - pos)upd(rt[pos], 1, m, x, y);
}
int kth(int u, int v,int k){
c1 = c2 = 0;
while(top[u] ^ top[v]){
if(dep[top[u]] < dep[top[v]])swap(u, v);
get(dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u, v);
get(dfn[u], dfn[v]); return qryk(1, m, k);
}
But honestly, in practice, this thing is used is really less, usually or cdq or transform the meaning of the question with a lower complexity of the approach to do.
Some advanced play with line trees
This part is mainly some other algorithms, ideas with the use of line tree, in fact, the main idea is still to find the nature of the topic, and then line tree optimization to maintain the information process.
So let's look at some lineage tree vs. dendritic stuff first.
Dendritic + Line Tree
Ever done a problem where you give some colors on a sequence to find the number of color segments, right? What happens if I throw it at the tree?
P2486 [SDOI2011] Staining
It turns out that it won't be any good at all. Straightforward tree dissection turns the tree into a chain do, sets up a line segmented tree and that's the end of it.
void add(int u, int v){
e[++cnt] = {hd[u], v}; hd[u] = cnt;
}
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1; sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top; dfn[u] = ++tim, rk[tim] = u;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
struct node{
int len, l, r;
};
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
lc[x] = lc[ls], rc[x] = rc[rs];
s[x] = s[ls] + s[rs] - (rc[ls] == lc[rs]);
}
void build(int x, int l, int r){
if(l == r)return(void)(lc[x] = rc[x] = a[rk[l]], s[x] = 1);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pd(int x){
if(! lz[x])return;
lc[ls] = rc[ls] = lz[x];
lc[rs] = rc[rs] = lz[x];
s[ls] = s[rs] = 1;
lz[ls] = lz[rs] = lz[x]; lz[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int c){
if(L <= l and r <= R)return(void)(lc[x] = rc[x] = lz[x] = c, s[x] = 1);
int mid = l + r >> 1; pd(x);
if(L <= mid)mdfy(ls, l, mid, L, R, c);
if(R > mid)mdfy(rs, mid + 1, r, L, R, c);
upd(x);
}
node qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return {s[x], lc[x], rc[x]};
int mid = l + r >> 1; node res, t; pd(x);
res = {0, 0, 0};
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid){
t = qry(rs, mid + 1, r, L, R);
if(! )return t;
+= - (rc[ls] == lc[rs]);
= ;
}
return res;
}
void mpath(int u, int v, int c){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
mdfy(1, 1, n, dfn[tp[u]], dfn[u], c);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
mdfy(1, 1, n, dfn[u], dfn[v], c);
}
int qpath(int u, int v){
int pr1 = 0, pr2 = 0, ans = 0;
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v), swap(pr1, pr2);
node res = qry(1, 1, n, dfn[tp[u]], dfn[u]);
ans += - (pr1 == );
pr1 = ; u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v), swap(pr1, pr2);
node res = qry(1, 1, n, dfn[u], dfn[v]);
ans += - (pr1 == ) - (pr2 == );
return ans;
}
Isn't this course a little too easy? Then strengthen it!
P3979 Distant Land
Now that's something to read!
Actually, the handling of color segments is not a problem, what we need to think about is how the changes in tree roots should be handled efficiently.
At this point we can categorize and discuss the location of the root of the tree. If the root of the tree is the point of inquiry then it is straightforward to output the global answer; if the root of the treeNot at the current point of inquiry\(u\) within the subtree of theIs that right?\(u\) It doesn't have any effect at all! In the end there is only one left - in\(u\) within one of the subtrees, at which point we definitely need to find which subtree it is first, and then just subtract that subtree globally.
So how do we find subtrees quickly? We can analogize the process of tree dissection to find LCAs and be done with it. Finding subtrees and other operations are\(O(n\log n)\) The.
void add(int u, int v){
e[++cnt] = {hd[u], v}; hd[u] = cnt;
}
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1; sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top; dfn[u] = ++tim, rk[tim] = u;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
mi[x] = min(mi[ls], mi[rs]);
}
void build(int x, int l, int r){
if(l == r)return(void)(mi[x] = a[rk[l]]);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pd(int x){
if(! lz[x])return;
mi[ls] = mi[rs] = lz[x];
lz[ls] = lz[rs] = lz[x]; lz[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int c){
if(L <= l and r <= R)return(void)(mi[x] = lz[x] = c);
int mid = l + r >> 1; pd(x);
if(L <= mid)mdfy(ls, l, mid, L, R, c);
if(R > mid)mdfy(rs, mid + 1, r, L, R, c);
upd(x);
}
ll qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return mi[x];
int mid = l + r >> 1; ll res = INF; pd(x);
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid)res = min(res, qry(rs, mid + 1, r, L, R));
return res;
}
void mpath(int u, int v, int c){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
mdfy(1, 1, n, dfn[tp[u]], dfn[u], c);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
mdfy(1, 1, n, dfn[u], dfn[v], c);
}
ll qtree(int u){
if(u == root)return mi[1];
if(dfn[root] < dfn[u] or dfn[root] >= dfn[u] + sz[u])return qry(1, 1, n, dfn[u], dfn[u] + sz[u] - 1);
int v = root;
while(tp[u] != tp[v]){
v = tp[v];
if(fa[v] == u)break;
v = fa[v];
}
if(tp[u] == tp[v])v = rk[dfn[u] + 1];
return min(qry(1, 1, n, 1, dfn[v] - 1), qry(1, 1, n, dfn[v] + sz[v], n));
}
Okay, it's time for a little bit of a question.
P2542 [AHOI2005] Route Planning
If you know LCT and have good coding skills it's recommended to just do it brainlessly and be done with it.
Consider what someone who doesn't know LCT would do. It's probably not practical to maintain deletion edges with a data structure or something, so consider doing it backwards to turn deletion edges into addition edges. Then there's the question of how to maintain the number of bridges between two points. I can get rid of the initial bridges, run a tarjan and the graph becomes a tree, and then consider what the add edge operation means. If I now need to convert the\((u,v)\) added to the diagram, then the tree\(u,v\) inter-Bridge on the PathIt's all gone, because it constitutes a ring. So each edge addition operation can be viewed as an interval assignment, and then the tree dissection sets a fruitful line tree done.
void addx(int u, int v){
ex[++cntx] = {hdx[u], v}; hdx[u] = cntx;
}
void tarjan(int u, int fa){
id[u] = low[u] = ++seq;
(u);
for(int i = hdx[u]; i; i = ex[i].nxt){
int v = ex[i].to;
if(v == fa)continue;
if(! id[v])tarjan(v, u);
low[u] = min(low[u], low[v]);
}
if(low[u] == id[u]){
++ct;
while(() ^ u){
col[()] = ct;
();
}
col[u] = ct; ();
}
}
void add(int u, int v){
e[++cnt] = {hd[u], v}; hd[u] = cnt;
}
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1; sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == f)continue;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int top){
tp[u] = top; dfn[u] = ++tim, rk[tim] = u;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
s[x] = s[ls] + s[rs];
}
void build(int x, int l, int r){
if(l == r)return(void)(s[x] = 1);
int mid = l + r >> 1;
build(ls, l, mid); build(rs, mid + 1, r);
upd(x);
}
void pd(int x, int l, int r){
if(! lz[x])return;
int mid = l + r >> 1;
s[ls] = s[rs] = 0;
lz[ls] = lz[rs] = lz[x]; lz[x] = 0;
}
void mdfy(int x, int l, int r, int L, int R, int c){
if(L <= l and r <= R)return(void)(s[x] = c, lz[x] = 1);
int mid = l + r >> 1; pd(x, l, r);
if(L <= mid)mdfy(ls, l, mid, L, R, c);
if(R > mid)mdfy(rs, mid + 1, r, L, R, c);
upd(x);
}
ll qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return s[x];
int mid = l + r >> 1, res = 0; pd(x, l, r);
if(L <= mid)res = qry(ls, l, mid, L, R);
if(R > mid)res += qry(rs, mid + 1, r, L, R);
return res;
}
void mpath(int u, int v, int c){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
mdfy(1, 1, n, dfn[tp[u]], dfn[u], c);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
mdfy(1, 1, n, dfn[u] + 1, dfn[v], c);
}
int qpath(int u, int v){
int res = 0;
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
res += qry(1, 1, n, dfn[tp[u]], dfn[u]);
u = fa[tp[u]];
}
if(dep[u] > dep[v])swap(u, v);
return res + qry(1, 1, n, dfn[u] + 1, dfn[v]);
}
signed main(){
n = rd(), m = rd();
for(int i = 1; i <= m; ++i){
E[i].u = rd(), E[i].v = rd();
if(E[i].u > E[i].v)swap(E[i].u, E[i].v);
++mp[mkp(E[i].u, E[i].v)];
}
while(1){
q[++tot][0] = rd();
if(q[tot][0] == - 1)break;
q[tot][1] = rd(), q[tot][2] = rd();
if(q[tot][1] > q[tot][2])swap(q[tot][1], q[tot][2]);
if(! q[tot][0])--mp[mkp(q[tot][1], q[tot][2])];
}
--tot;
for(int i = 1; i <= m; ++i){
int u = E[i].u, v = E[i].v;
if(mp[mkp(u, v)])addx(u, v), addx(v, u);
}
tarjan(1, 0);
for(int i = 1; i <= m; ++i){
int u = E[i].u, v = E[i].v;
if(mp[mkp(u, v)] and col[u] ^ col[v])add(col[u], col[v]), add(col[v], col[u]);
}
for(int i = 1; i <= tot; ++i)q[i][1] = col[q[i][1]], q[i][2] = col[q[i][2]];
dfs1(1, 0); dfs2(1, 1); build(1, 1, n);
for(int i = tot; i; --i){
if(q[i][0])ans[++tt] = q[i][1] == q[i][2] ? 0 : qpath(q[i][1], q[i][2]);
else mpath(q[i][1], q[i][2], 0);
}
for(int i = tt; i; --i)printf("%d\n", ans[i]);
return 0;
}
P4211 [LNOI2014] LCA
For this kind of question we need to translate the information of the question.
Can we look at the process of finding the depth of lca at two points like in the text in a different light? We can think of it as adding one to the path from one point to the root, and the other point then querying the sum of the weights of its path to one. Then it's good to do. Specifically, we can convert the interval and the point to find the depth of lca into two prefixes and subtract, which is not directly offline after the scanning line to sweep the matter?
void dfs1(int u, int f){
dep[u] = dep[f] + 1, sz[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
dfs1(v, u); sz[u] += sz[v];
if(sz[son[u]] < sz[v])son[u] = v;
}
}
void dfs2(int u, int tp){
top[u] = tp, dfn[u] = ++tim, rk[tim] = u;
if(son[u])dfs2(son[u], tp);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to; if(v ^ son[u])dfs2(v, v);
}
}
int s[N << 2], tg[N << 2];
#define ls x << 1
#define rs x << 1 | 1
int ad(int x, int y){
return x += y, x >= p ? x - p : x;
}
void upd(int x){
s[x] = ad(s[ls], s[rs]);
}
void pd(int x, int l, int r){
if(! tg[x])return; int mid = l + r >> 1;
tg[ls] = ad(tg[ls], tg[x]), tg[rs] = ad(tg[rs], tg[x]);
s[ls] = ad(s[ls], tg[x] * (mid - l + 1) % p);
s[rs] = ad(s[rs], tg[x] * (r - mid) % p);
return(void)(tg[x] = 0);
}
void mdf(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return(void)(s[x] = ad(s[x], (r - l + 1) >= p ? r - l + 1 - p : r - l + 1), ++tg[x]);
int mid = l + r >> 1; pd(x, l, r);
if(ql <= mid)mdf(ls, l, mid, ql, qr);
if(mid < qr)mdf(rs, mid + 1, r, ql, qr);
upd(x);
}
int qry(int x, int l, int r, int ql, int qr){
if(ql <= l and r <= qr)return s[x];
int mid = l + r >> 1, res = 0; pd(x, l, r);
if(ql <= mid)res = qry(ls, l, mid, ql, qr);
if(mid < qr)res = ad(res, qry(rs, mid + 1, r, ql, qr));
return res;
}
void up(int u){
while(top[u] ^ 1){
mdf(1, 1, n, dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
mdf(1, 1, n, 1, dfn[u]);
}
int fd(int u){
int sum = 0;
while(top[u] ^ 1){
sum = ad(sum, qry(1, 1, n, dfn[top[u]], dfn[u]));
u = fa[top[u]];
}
return ad(sum, qry(1, 1, n, 1, dfn[u]));
}
struct qay{
int x, id, o;
};
vector < qay > q[N];
int ans[N];
int main(){
rd(n, Q);
for(int i = 2; i <= n; ++i)rd(fa[i]), add(++fa[i], i);
dfs1(1, 0), dfs2(1, 1);
for(int i = 1, l, r, x; i <= Q; ++i){
rd(l, r, x);
q[++r].pb({++x, i, 1});
q[l].pb({x, i, - 1});
}
for(int i = 1; i <= n; ++i){
up(i);
for(qay j : q[i])ans[] = (ans[] + p + * fd()) % p;
}
for(int i = 1; i <= Q; ++i)wt(ans[i]), pc('\n');
return 0;
}
P4069 [SDOI2016] Games
I feel like the questions I'm looking for are too easy.
It may be useful to see the modified equation with a\(dis\) You'll immediately think of difference, but on second thought that doesn't seem right. Because it asks for the path minimum each time, but each operation is relatively independent, at this glance do you think this is more of a line covering question.
Figured out the practice of this question on the call, direct tree dissections set Li Chao line segment tree board to do the end. But add line segment place also in lca disposition discussion.
void dfs1(int u, int f){
dep[u] = dep[fa[u] = f] + 1; cnt[u] = 1;
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to; if(v == f)continue; dis[v] = dis[u] + e[i].w;
dfs1(v, u); if(cnt[son[u]] < cnt[v])son[u] = v;
cnt[u] += cnt[v];
}
}
void dfs2(int u, int top){
tp[u] = top;
dfn[u] = ++seq; rk[dfn[u]] = u;
if(! son[u])return; dfs2(son[u], top);
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to;
if(v == fa[u] or v == son[u])continue;
dfs2(v, v);
}
}
int lca(int u, int v){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
u = fa[tp[u]];
}
return dep[u] < dep[v] ? u : v;
}
ll k[N], b[N], c[N << 3];
#define ls x << 1
#define rs x << 1 | 1
ll calc(int x, int pos){
return k[x] * dis[rk[pos]] + b[x];
}
bool cmp(int x1, int x2, int pos){
ll a = calc(x1, pos), b = calc(x2, pos);
return a < b or (a == b and x1 < x2);
}
void updd(int x, int l, int r){
ll a = calc(sgt[x], l), b = calc(sgt[x], r);
c[x] = min(c[x], min(a, b));
c[x] = min(c[x], min(c[ls], c[rs]));
}
void _upd(int tmp, int x, int l, int r){
int mid = l + r >> 1;
if(cmp(tmp, sgt[x], mid))swap(tmp, sgt[x]);
if(cmp(tmp, sgt[x], l))_upd(tmp, ls, l, mid);
if(cmp(tmp, sgt[x], r))_upd(tmp, rs, mid + 1, r);
updd(x, l, r);
}
void upd(int x, int l, int r, int L, int R, int tmp){
if(L <= l and r <= R)return _upd(tmp, x, l, r);
int mid = l + r >> 1;
if(L <= mid)upd(ls, l, mid, L, R, tmp);
if(R > mid)upd(rs, mid + 1, r, L, R, tmp);
updd(x, l, r);
}
ll qry(int x, int l, int r, int L, int R){
if(L <= l and r <= R)return c[x];
int mid = l + r >> 1; ll res = min(calc(sgt[x], max(l, L)), calc(sgt[x], min(r, R)));
if(L <= mid)res = min(res, qry(ls, l, mid, L, R));
if(R > mid)res = min(res, qry(rs, mid + 1, r, L, R));
return res;
}
void usum(int u, int v, int tmp){
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
upd(1, 1, n, dfn[tp[u]], dfn[u], tmp);
u = fa[tp[u]];
}
if(dfn[u] < dfn[v])swap(u, v);
upd(1, 1, n, dfn[v], dfn[u], tmp);
}
ll qsum(int u, int v){
ll res = INF;
while(tp[u] != tp[v]){
if(dep[tp[u]] < dep[tp[v]])swap(u, v);
res = min(res, qry(1, 1, n, dfn[tp[u]], dfn[u]));
u = fa[tp[u]];
}
if(dfn[u] < dfn[v])swap(u, v);
res = min(res, qry(1, 1, n, dfn[v], dfn[u]));
return res;
}
signed main(){
for(int i = 0; i < N << 3; ++i)c[i] = INF;
n = rd(), m = rd(); int lcnt = 0;
for(int i = 1; i < n; ++i){
int u = rd(), v = rd(); ll w = rd();
add(u, v, w); add(v, u, w);
}
dfs1(1, 0); dfs2(1, 1); b[0] = INF;
for(int i = 1; i <= m; ++i){
int op = rd(), u = rd(), v = rd();
if(op ^ 1)printf("%lld\n", qsum(u, v));
else{
int t = lca(u, v);
ll A = rd(), B = rd();
k[++lcnt] = - A; b[lcnt] = A * dis[u] + B;
usum(u, t, lcnt);
k[++lcnt] = A; b[lcnt] = A * (dis[u] - 2 * dis[t]) + B;
usum(t, v, lcnt);
}
}
return 0;
}
Line segment tree with dp
I won't go into all the dp-related tips and knowledge here, so you can look up some of the blogs I've written about dp. This is a threaded tree topic, so I want to talk a little bit about threaded trees.
First is the question of when to use the line tree. If something comes up in the dp formula that requires an onion interval transfer we'll think about memorizing the key information first and merge it directly when we transfer it, when we can't find or merge it fast enough we'll go up the line tree.
Then there's the question of what does a line segment tree need to maintain? The original purpose of enabling the segment tree is to maintain some information that is not well recorded in an array, or something that is not convenient to transfer or query. So we should combine the actual records in the process of maintaining the line tree, rather than throwing the original information in as is. For example, if the original information has good properties after differentiation, I just need to throw in the difference and merge it when querying.
The last thing is what line segment tree to choose. When we maintain information that is only mergeable we go to the most common line tree, if the information has some additive or subtractive properties we can consider persistence. If the information is high-dimensional, we will first see if we can cdq it, then look at the tree nesting tree, and finally consider the kd-tree (although I don't know how to do this, so I just have to look at it).
P1442 Iron ball falling to the ground
Since I did this a long time ago and wrote the problem solving, this is an excerpt from the original problem solving at the time.
Since the iron ball falls from high to low, then the shortest time contribution from each platform will only originate from the platform (or platforms) above it, so it is linear, so consider dp.
Consider dp in descending order. order\(dp[i][0/1]\) denote\(x\) Axis to the first\(i\) Minimum time for the left/right endpoints of a platform.
It is first possible to introduce the first\(i\) Any point on the platform\((k,a_i.h)\) until (a time)\(x\) The shortest time spent on the axis is:\(\min(k-a_i.l+dp[i][0],a_i.r-k+dp[i][1])\)
Then inter-platform transfer:
It is then possible to use the data structure to maintain\(j\) up. Specifically, each update\(i\) The answer to this question overwrites the previous platform number with the current platform number, but the data is too large and needs to be discretized a bit. Maintenance is done with a line tree andset Both.
So that's how this question was used by meset Watered down. But since I'm very responsible I'll put a code anyway:
int n, m, x, y, f[N][2];
struct line{
int h, l, r;
}a[N];
set < pair < int, int > > s;
bool cmp(line x, line y){
return < ;
}
void upd(int &ff, int nw, int h, int j){
if(h - a[j].h > m)return;
if(! j)return(void)(ff = h);
ff = h - a[j].h + min(nw - a[j].l + f[j][0], a[j].r - nw + f[j][1]);
}
signed main(){
n = rd(); m = rd(); x = rd(); y = rd();
for(int i = 1; i <= n; ++i)a[i].h = rd(), a[i].l = rd(), a[i].r = rd();
memset(f, INF, sizeof f); sort(a + 1, a + 1 + n, cmp);
({INF, 0});
for(int i = 1; i <= n; ++i){
int lx = a[i].l, rx = a[i].r, hx = a[i].h;
auto lp = s.lower_bound({lx, 0}), rp = s.lower_bound({rx, 0});
upd(f[i][0], lx, hx, lp -> second); upd(f[i][1], rx, hx, rp -> second);
int tg = lp -> second;
for(; lp -> first <= rx; lp = (lp)); ({lx, tg}); ({rx, i});
}
int res; upd(res, x, y, s.lower_bound({x, 0}) -> second);
printf("%d", res);
return 0;
}
Look at a canonical question.
P4655 [CEOI2017] Building Bridges
This dp seems to be pretty much at a glance.
found\(f_i\) denote\(1\) walk\(i\) of the minimum cost, and then the transfer equation is:
do sth (for sb)\(w\) Remembering a prefix and and splitting the equation a bit, it becomes:
Then bring up the unchanging ones:
The goal now is to find out how to quickly query\(\min\). If you are interested in every\(j\) Think of everything related to it as a function, and then think of the\(i\) pertinent\(h_i\) Looking at it as a variable, do I just put\(\min\) The lump in there abstracts into a single function. I made\(k=h_j,b=f_j+h_j^2-s_j\)And then the pile became\(k\times h_i+b\)The problem then becomes to look up the position among all the current line segments\(h_i\) at the minimum value, so it's a Lee Hyperlinear Tree.
int n;
ll h[N], w[N];
ll s[N], f[N];
namespace SGT{
ll k[N], b[N];
int sgt[M << 2];
#define ls x << 1
#define rs x << 1 | 1
const int lim = M - 3;
ll calc(int x, int pos){return k[x] * pos + b[x];}
bool cmp(int x1, int x2, int pos){
ll t1 = calc(x1, pos), t2 = calc(x2, pos);
return t1 < t2;
}
void upd(int x, int l, int r, int id){
int mid = l + r >> 1;
if(cmp(id, sgt[x], mid))swap(sgt[x], id);
if(cmp(id, sgt[x], l))upd(ls, l, mid, id);
if(cmp(id, sgt[x], r))upd(rs, mid + 1, r, id);
}
void mdf(int x, int l, int r, int ql, int qr, int id){
if(ql <= l and r <= qr)return(void)(upd(x, l, r, id));
int mid = l + r >> 1;
if(ql <= mid)mdf(ls, l, mid, ql, qr, id);
if(mid < qr)mdf(rs, mid + 1, r, ql, qr, id);
}
int qry(int x, int l, int r, int pos){
if(l == r)return sgt[x];
int mid = l + r >> 1, res;
res = pos <= mid ? qry(ls, l, mid, pos) : qry(rs, mid + 1, r, pos);
return cmp(res, sgt[x], pos) ? res : sgt[x];
}
}
using namespace SGT;
int main(){
rd(n); for(int i = 1; i <= n; ++i)rd(h[i]); b[0] = inf;
for(int i = 1; i <= n; ++i)rd(w[i]), s[i] = s[i - 1] + w[i];
for(int i = 1; i <= n; ++i){
int j = qry(1, 0, lim, h[i]);
if(i ^ 1)f[i] = f[j] + h[j] * h[j] - s[j] - 2 * h[i] * h[j] + h[i] * h[i] + s[i - 1];
k[i] = - 2 * h[i]; b[i] = f[i] + h[i] * h[i] - s[i];
mdf(1, 0, lim, 0, lim, i);
}
wt(f[n]);
return 0;
}
Problem - 1476F - Codeforces
warrant (law)\(f_i\) preindex\(i\) The largest prefix that a lamp can illuminate. Consider shifting.
For the current lamp there are two cases, one is the previous lamp can not illuminate it, then do not care directly skip, there is the illumination to update the current maximum value.
But there's actually another one where the current one is facing left, and then whatever can be illuminated by it is all to the right, when the\(f_i=\max_{i-p_i\le j<i}\{j+p_j\}\)。
Then it's actually maintained with the st table, but this question has some value so I'll put it here.
The final output program just works backwards once.
void init(int nn){
f[0] = f[1] = 0;
for(int i = 1; i <= nn; ++i)op[i] = 0;
}
void make_st(){
for(int j = 1; j <= lg[n]; ++j)
for(int i = 1; i + (1 << j) - 1 <= n; ++i)st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
int query(int l, int r){
if(l > r)return 0;
int j = lg[r - l + 1];
return max(st[l][j], st[r - (1 << j) + 1][j]);
}
int find(int l, int r, int x){
int id = - 1;
while(l <= r){
int mid = l + r >> 1;
if(f[mid] >= x)id = mid, r = --mid;
else l = ++mid;
}
return id;
}
void solve(int x){
if(! x)return;
if(f[x] == f[x - 1])return (void)solve(x - 1);
if(f[x] == st[x][0] and f[x - 1] >= x)return (void)(op[x] = 1, solve(x - 1));
int y = find(0, x - 1, x - p[x] - 1);
for(int i = y + 1; i < x; ++i)op[i] = 1;
solve(y);
}
signed main(){
ios::sync_with_stdio(false);
(nullptr);
int T; cin >> T;
for(int i = 2; i < N; ++i)lg[i] = lg[i >> 1] + 1;
while(T--){
init(n);
cin >> n;
for(int i = 1; i <= n; ++i)cin >> p[i], st[i][0] = i + p[i];
make_st();
for(int i = 1; i <= n; ++i){
f[i] = f[i - 1];
if(f[i] >= i)f[i] = max(f[i], st[i][0]);
int id = find(0, i - 1, i - p[i] - 1);
if(id != - 1)f[i] = max(f[i], max(i - 1, query(id + 1, i - 1)));
}
// for(int i = 1; i <= n; ++i)cout << "f[" << i << "] = " << f[i] << ' '; cout << '\n';
if(f[n] < n){
cout << "NO" << '\n';
continue;
}
cout << "YES" << '\n';
solve(n);
for(int i = 1; i <= n; ++i)cout << (op[i] ? 'R' : 'L');
cout << '\n';
}
return 0;
}
Line Tree Optimization for Graph Building
As the name suggests, it is in the process of building the graph may appear points to the interval connected to the edge or the interval to the point connected to the edge of the situation, then you need to optimize the construction of the graph of the line tree, just the graph of the complexity of the operation of a more than one\(\log\)。
Problem - 786B - Codeforces
This question is where the above situation arises, and the focus here is on the method of building the graph. First of all, we need to meet the interval can be linked to the point, which requires the nodes of the line tree and the point to be connected. We can follow the line tree to maintain information in the way, the nodes of the tree layer by layer connected, and finally the leaf nodes actually represent the real point.
The second is that these imaginary edges that we multi-connect cannot affect the answer. This is where the design of the edge weights needs to be carefully considered. For example, if this question is for the shortest circuit, so I set the edge weights to zero, then if we are running a network flow, our edge weights (capacity) should be set to positive infinity.
The following code shows only the concatenated edge method, and I believe that readers who are able to see this will be the most short-circuited.
void build(int x, int l, int r){
t[x].l = l, t[x].r = r;
if(l == r){
int n1 = l + (n << 3), n2 = x + (n << 2);
add(n1, x, 0); add(x, n1, 0);
add(n1, n2, 0); add(n2, n1, 0);
return;
}
int mid = l + r >> 1, t = n << 2;
add(x, ls, 0); add(x, rs, 0);
add(ls + t, x + t, 0); add(rs + t, x + t, 0);
build(ls, l, mid); build(rs, mid + 1, r);
}
void modify(int x, int L, int R, int u, ll w, bool op){
int l = t[x].l, r = t[x].r, mid = l + r >> 1;
int t1 = n << 2, t2 = n << 3;
if(L == l and r == R){
if(op)return (void)(add(x + t1, u + t2, w));
else return (void)(add(u + t2, x, w));
}
if(R <= mid)modify(ls, L, R, u, w, op);
else if(L > mid)modify(rs, L, R, u, w, op);
else{
modify(ls, L, mid, u, w, op);
modify(rs, mid + 1, R, u, w, op);
}
}
signed main(){
//freopen(,stdin);
//freopen(,stdout);
ios::sync_with_stdio(false);
(nullptr);
cin >> n >> q >> s;
build(1, 1, n);
for(int i = 1, op, u, v, l, r; i <= q; ++i){
cin >> op >> u;
ll w;
if(op == 1){
cin >> v >> w;
add(u + (n << 3), v + (n << 3), w);
}
else{
cin >> l >> r >> w;
modify(1, l, r, u, w, op - 2);
}
}
s += (n << 3);
dijkstra();
for(int i = 1, t = n << 3; i <= n; ++i){
if(d[i + t] < 2e18)cout << d[i + t] << ' ';
else cout << - 1 << ' ';
}
return 0;
}
P6348 [PA2011] Journeys
Problem Escalation! What if it is an interval to interval concatenated edge? If the interval is captured out corresponding to the connected is\(O(\log^2)\) and then the bfs is also\(O(\log^2)\) s so it gets stuck. At this point we can just go ahead and build the imaginary point and edge the interval to the imaginary point.
void build(int x, int l, int r){
t[x].l = l, t[x].r = r;
if(l == r)return (void)(id[l] = x);
int mid = l + r >> 1, t = n << 2;
add(x, ls, 0); add(x, rs, 0);
add(ls + t, x + t, 0); add(rs + t, x + t, 0);
build(ls, l, mid); build(rs, mid + 1, r);
}
void modify(int x, int L, int R, int u, bool op){
int l = t[x].l, r = t[x].r, mid = l + r >> 1;
if(l == L and r == R){
if(op)return (void)(add(x + (n << 2), u, 0));
return (void)(add(u, x, 0));
}
if(R <= mid)modify(ls, L, R, u, op);
else if(L > mid)modify(rs, L, R, u, op);
else{
modify(ls, L, mid, u, op);
modify(rs, mid + 1, R, u, op);
}
}
signed main(){
//freopen(,stdin);
//freopen(,stdout);
ios::sync_with_stdio(false);
(nullptr);
cin >> n >> m >> s;
build(1, 1, n);
cnt = n << 3;
for(int i = 1, l1, l2, r1, r2; i <= m; ++i){
int u = ++cnt, v = ++cnt;
cin >> l1 >> r1 >> l2 >> r2;
add(v, u, 1); modify(1, l2, r2, u, 0); modify(1, l1, r1, v, 1);
u = ++cnt, v = ++cnt;
add(v, u, 1); modify(1, l1, r1, u, 0); modify(1, l2, r2, v, 1);
}
for(int i = 1, t = n << 2; i <= n; ++i){
add(id[i], id[i] + t, 0);
add(id[i] + t, id[i], 0);
}
s = id[s] + (n << 2);
bfs();
for(int i = 1; i <= n; ++i)cout << d[id[i]] << '\n';
return 0;
}
after thatStation classificationEveryone should have done it, right? If you change its data range to\(n=10^5\) And what to do?
Consider a line segment tree optimized for building graphs. Each trip is equivalent to some intervals connecting edges to some points, just like the question above, each time a new virtual point is created, intervals connect to virtual points, virtual points connect to a single point. Only because we want to run toposort, so the edges in the line tree need to be changed to unidirectional edges, then note that the direction must be from the leaves to the root. I'm too lazy to find the code, so I won't put it.
More difficult applications of line trees (miscellaneous questions)
P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces
A very good question!
First find the nature of the topic, then realize that operation 1 can be merged, so only consider how to do operation 1 quickly and get the answer to operation 2. Consider first how to maintain color segments on dynamic sequences, we can maintain segments that satisfy\(col_{i-1}=col_{i}=col_{i+1}\) The answer is to subtract the total number of the intervals from the number of the intervals. For the endpoints of the interval we'll just judge violently because it won't be more than\(O(\log n)\). So what about operation one?
Consider that some intervals are exchanged after each operation but some areremain relatively stationary, then it is recommended to write down a few random numbers to operate with paper and pen by hand.
You'll see that I actually put\([0,1]\) This interval pans out to the\([6,7]\), others can be analogized. Imagine for a segment of a line tree of length\(len\) The only thing that would happen after I did operation one would be the\(len\) Species. Setting up a different or upper\(sum\)if\(sum>len\) It can actually be seen as\(sum\bmod len\), because by putting all these things in binary you realize that all those extra digits of one he has are useless, and the\(sum\) take zero or more (in calculus)\(len-1\) The transformations of the time series are again different from each other, so there are\(len\) kind of situations. And then I can actually just write down those cases. The time complexity is\(\sum_{i=0}^{2^i\le len}\frac{len}{2^i}=2\times len\) s, so the total complexity of tree building is still\(O(n\log n)\) The.
Then actually go directly on the line tree on the line, for the query to the interval, if the value of the current operation is less than or equal to the answer can be taken out directly, otherwise you need topanningto a point in the same layer, calling its answer. How do we handle this for translation operations?
We can record an array\(jump_{l,i}\) represents the left endpoint on the sequence as\(l\) and the size of the line segment tree node is\(2^i\) who is the point of the jump, and then the jump is equivalent to the binary under theThe number of digits is less than or equal to the current point of travelJust call the answer directly after the translation, the part that is greater than or equal to isomorphic to the left endpoint of the upper interval jump directly, and the final midpoint of the answer is just violently merged.
(If a little dizzy it is recommended to draw it in conjunction with the diagram above)
Code:
void bld(int x, int l, int r){
int len = r - l, mid = l + r >> 1;
jump[l][lg[len]] = x; f[x].rsz(len);
if(l + 1 == r)return;
bld(ls, l, mid), bld(rs, mid, r);
for(int i = 0; i < len; ++i)
if(i < (len >> 1))f[x][i] = f[ls][i] + f[rs][i] + (a[mid - 1 ^ i] == a[mid ^ i]);
else f[x][i] = f[ls][i - (len >> 1)] + f[rs][i - (len >> 1)] + (a[mid - 1 ^ i] == a[mid ^ i]);
}
int qry(int x, int l, int r, int ql, int qr){
if(ql <= l and r - 1 <= qr)return f[jump[l ^ (opt >> lg[r - l] << lg[r - l])][lg[r - l]]][opt % (1 << lg[r - l])];
int mid = l + r >> 1, ansl(0), ansr(0); bool fl(false), fr(false);
if(ql < mid)fl = true, ansl = qry(ls, l, mid, ql, qr);
if(mid <= qr)fr = true, ansr = qry(rs, mid, r, ql, qr);
return fl ? (fr ? (ansl + ansr + (a[mid ^ opt] == a[mid - 1 ^ opt])) : ansl) : ansr;
}
P2757 [NCT] Equivariant subsequences
The nature of this problem is to consider just three numbers that satisfy the condition. Then the number in the center is the most special! Because the input numbers form an arrangement, suppose I color all the dots to the left of the current point black (1) and all the dots to the right white (0) if\(\exists t,col_{x+t}=1,col_{x-t}=0\) Then it means find it.
Then we consider how to quickly find and update. If I color the position as above, how do I determine this quickly? I can color in the value field, think of this 01 sequence as a high number, in practice I can maintain a high number for each of the black and white dots, and then go to compare them to see if a certain number of digits are palindromes. If you think about it, isn't this just hashing to determine the palindrome? So the two line trees maintain forward/backward hash on the line.
But because of the watery data in the past, I usedbitset Fucked up and now too lazy to write code so goo.
P4197 Peaks
Observe that the restriction is\(\le x\) So let's go straight offline down sorting by restriction from smallest to largest then line tree merge violently do it.
P7834 [ONTAK2010] Peaks Enhanced EditionConsider strengthening
Now you can't go offline. And what should you do?
In fact, the approach is still based on the limitations of this question\(\le x\)We can build kruskal reconstruction trees because of this relationship. Because of this relationship, we can build kruskal reconstruction trees. This way, if two points can reach each other if and only if their lca is less than or equal to x, we jump up from the current point until we can't go to any other point. This process can be achieved by multiplication, and multiplication maintains a maximum value. Then once we've reached the highest point, we can just query it using the chair tree.
struct Edge{
int u, v; ll w;
friend bool operator < (Edge a, Edge b){
return < ;
}
}E[M];
struct edge{
int nxt, to;
}e[M << 1];
void add(int u, int v){
e[++cnt] = {hd[u], v}, hd[u] = cnt; ++in[v];
}
int fd(int x){
return x == ff[x] ? x : ff[x] = fd(ff[x]);
}
void dfs(int u, int fa){
lq[dfn[++tim] = u] = tim, f[u][0] = fa;
for(int i = 1; (1 << i) <= n; ++i)f[u][i] = f[f[u][i - 1]][i - 1];
for(int i = hd[u]; i; i = e[i].nxt){
int v = e[i].to; if(v == fa)continue;
dfs(v, u), sz[u] += sz[v];
}
if(! sz[u])sz[u] = 1; rq[u] = tim;
}
int rt[N], ls[N << 5], rs[N << 5], t[N << 5];
void upd(int &x, int y, int l, ll r, int pos, int val){
if(! x)x = ++tot; t[x] = t[y] + val;
if(l == r)return; ll mid = l + r >> 1;
if(pos <= mid)rs[x] = rs[y], upd(ls[x], ls[y], l, mid, pos, val);
else ls[x] = ls[y], upd(rs[x], rs[y], mid + 1, r, pos, val);
}
int kth(int x, int y, int l, ll r, int k){
if(l == r)return l; ll mid = l + r >> 1, s = t[rs[y]] - t[rs[x]];
if(k > s)return kth(ls[x], ls[y], l, mid, k - s);
else return kth(rs[x], rs[y], mid + 1, r, k);
}
int qry(int u, int lim, int k){
for(int i = 23; ~ i; --i)if(f[u][i] and c[f[u][i]] <= lim)u = f[u][i];
if(sz[u] < k)return - 1;
return kth(rt[lq[u] - 1], rt[rq[u]], 0, inf, k);
}
signed main(){
// fileio(fil);
int mod;
mod = n = rd(), m = rd(), q = rd();
for(int i = 1; i <= n; ++i)h[i] = rd();
for(int i = 1; i <= (n << 1); ++i)ff[i] = i;
for(int i = 1; i <= m; ++i){
int u = rd(), v = rd(); ll w = rd();
E[i] = {u, v, w};
}
sort(E + 1, E + 1 + m);
for(int i = 1; i <= m; ++i){
int u = fd(E[i].u), v = fd(E[i].v); ll w = E[i].w;
if(u == v)continue;
ff[u] = ff[v] = ++n; c[n] = w;
add(n, u), add(n, v);
}
for(int i = 1; i <= n; ++i)if(! in[i])dfs(i, 0);
for(int i = 1; i <= n; ++i){
if(dfn[i] <= mod)upd(rt[i], rt[i - 1], 0, inf, h[dfn[i]], 1);
else rt[i] = rt[i - 1];
}
ll lastans = 0;
for(int i = 1; i <= q; ++i){
ll u = (rd() ^ lastans) % mod + 1, lim = rd() ^ lastans, k = (rd() ^ lastans) % mod + 1;
printf("%lld\n", lastans = qry(u, lim, k)); lastans = max(0ll, lastans);
}
return 0;
}
P4898 [IOI2018] seats Rows of seats
The verdict is: really god questions!
What we need to think about is how to translate the title. Let's assume that the seats that have been assigned are ones (black dots) and zeros (white dots) otherwise. The normal idea is analogous to the one-dimensional when we record the number of ones in the interval and see if it is equal to the size of the interval. This can be maintained in a line segment tree. But considering that the operation of switching seats affects a segment of the interval, if I each have to\(O(1)\) The modification must have blown up, and we would have needed a kind ofInformation that can be mergedGoing to replace the current one.
With interval operations we can think of interval addition, so can we now record some addable information to describe the legal situation?
Let's consider the case of each point, assuming that the current state has been legal and is now a rectangle then there may be a circle of white dots around it. Assuming the point is black, think about what properties it satisfies when the rectangle is legal and when the rectangle is not. Here's the best part of this problem! We can focus on the state of the points around it to determine if it is legal or not. Specifically, if the point to the left of the point and the point above it have black dots, then it can only be part of the rectangle, otherwise it must be the upper-left corner of the rectangle, and there is obviously only one upper-left corner. That means we have to maintain the black pointBlack spots with white dots on the left and on the topthe number of times the condition is satisfied when the number is one.
Then consider the state around the white dot. If it is surrounded by at least two black dots then the current state is not legal. So we can record it againA white dot surrounded by at least two black dotsThe condition is satisfied when the quantity is zero.
Then smart as you are, you'll realize that both states need to be satisfied at the same time, so you can maintain them together. The last thing is to support interval addition and query the number of global minima. The modification operation is really just a matter of violently swapping around some points that might be affected, and just recalculating those points.
const int dir[4][2] = {1, 0, - 1, 0, 0, 1, 0, - 1};
int h, w, q;
vector < vector < int > > g;
int tt[N];
struct node{
int x, y, tim;
}a[N];
int res[N << 2], cnt[N << 2], tg[N << 2];
#define ls x << 1
#define rs x << 1 | 1
void upd(int x){
res[x] = min(res[ls], res[rs]);
cnt[x] = cnt[ls] * (res[x] == res[ls]) + cnt[rs] * (res[x] == res[rs]);
}
void init(int x, int l, int r){
if(l == r)return(void)(cnt[x] = 1);
int mid = l + r >> 1;
init(ls, l, mid), init(rs, mid + 1, r);
upd(x);
}
void pd(int x){
if(! tg[x])return;
tg[ls] += tg[x], res[ls] += tg[x];
tg[rs] += tg[x], res[rs] += tg[x];
return(void)(tg[x] = 0);
}
void mdf(int x, int l, int r, int ql, int qr, int y){
if(ql <= l and r <= qr)return(void)(res[x] += y, tg[x] += y);
int mid = l + r >> 1; pd(x);
if(ql <= mid)mdf(ls, l, mid, ql, qr, y);
if(mid < qr)mdf(rs, mid + 1, r, ql, qr, y);
upd(x);
}
int get(int x, int y){
if(x < 0 or y < 0 or x >= h or y >= w)return inf;
return a[g[x][y]].tim;
}
int loc(int x, int y){
if(x < 0 or y < 0 or x >= h or y >= w)return - 1;
return g[x][y];
}
void option(int i, int op){
vector < int > lp; int t1, t2;
(get(a[i].x + 1, a[i].y));
(get(a[i].x, a[i].y + 1));
(t1 = get(a[i].x - 1, a[i].y));
(t2 = get(a[i].x, a[i].y - 1));
sort((), ()); int lpos = lp[1];
if(a[i].tim > lpos)mdf(1, 1, h * w, lpos, a[i].tim - 1, op);
t1 = min(t1, t2); if(t1 > a[i].tim)mdf(1, 1, h * w, a[i].tim, t1 - 1, op);
}
int main(){
rd(h, w, q); (h); for(int i = 0; i < h; ++i)g[i].rsz(w);
for(int i = 1; i <= h * w; ++i){
rd(a[i].x, a[i].y);
g[a[i].x][a[i].y] = a[i].tim = i;
tt[i] = i;
}
init(1, 1, h * w);
for(int i = 1; i <= h * w; ++i)option(i, 1);
for(int i = 1, u, v; i <= q; ++i){
rd(u, v); ++u, ++v;
int used[12], cc;
used[1] = u = tt[u], used[cc = 2] = v = tt[v];
int xx = a[u].x, yy = a[u].y;
for(int j = 0; j < 4; ++j){
int tmp = loc(xx + dir[j][0], yy + dir[j][1]);
if(~ tmp)used[++cc] = tmp;
}
xx = a[v].x, yy = a[v].y;
for(int j = 0; j < 4; ++j){
int tmp = loc(xx + dir[j][0], yy + dir[j][1]);
if(~ tmp)used[++cc] = tmp;
}
sort(used + 1, used + 1 + cc); cc = unique(used + 1, used + 1 + cc) - used - 1;
for(int j = 1; j <= cc; ++j)option(used[j], - 1);
swap(a[u].tim, a[v].tim);
swap(tt[a[u].tim], tt[a[v].tim]);
for(int j = 1; j <= cc; ++j)option(used[j], 1);
wt(cnt[1]); pc('\n');
}
return 0;
}
postscript
It took me two days from the start of the draft (2024.11.6 16:00) to completion (2024.11.8.15.26). During that time I wrote about ten questions and refreshed what I had taught over the summer and pulled out on the 4th of Julyalmost allAll the questions, but of course some of them were too counterintuitive for me to finish. Starting tomorrow, I'm going to review the dp section, but it will probably be hard to write thousands of words like I did this time. This afternoon, with the half-term exams coming to an end, students who have not been suspended will return to the team one after another, and the computer room will no longer be cold. But this quiet devotion to do a thing is really good! Every day back to the dormitory is very tired, at night Sin a bath, lie down and go to sleep, always wake up at 6:30 in the morning on time, so the biological clock is formed.
I wonder how long it will be until I have so much inner peace again? Perhaps changing your mindset is both a challenge and a gift. When you succeed in overcoming your ego, you may reap unexpected surprises!
But anyway, the ds side of the content is sort of finished. cdq and overall dichotomy I will finish reviewing in the second half of this afternoon, the next very systematic review should be after the noip, I hope not to give myself regrets, but also hope that everyone can have a bright future!