I ran it using CF custom test, with different compilers, the results are different:

GNU C++11 5.1.0:

6 5 0 0 0 

GNU C++14 6.4.0:

6 5 0 0 2 

GNU C++17 7.3.0 / Clang++17 Diagnostics:

6 5 4 3 2 

Microsoft Visual C++ 2010 / Microsoft Visual C++ 2017:

Runtime error: exit code is -1073741819

After asking yhx-12243 for help, I got the reason: the order of evaluation of assignment statement in C++ is unspecific.

In the above case, the push_back function called in foo(p-1) caused a reallocation, and the left part bar[x] is no longer validated, thus the error occurred.

Then, I googled for it and found it on Stack Overflow. You can read the accepted answer there for more information.

As a conclusion:

1. In assignment statements, it's better to avoid possible changes happens in the right part which affect the left part, and vice versa.

2. Beware of iterator validity, for example, after push_back, the old iterators may be invalidated.

42 421
1 2 1 0
1 3 3 0
1 4 5 0
1 5 10 0
1 6 20 0
1 7 40 0
1 8 80 0
1 9 160 0
1 10 320 0
1 11 640 0
1 12 1280 0
1 13 2560 0
1 14 5120 0
1 15 10240 0
1 16 20480 0
1 17 40960 0
1 18 81920 0
1 19 163840 0
1 20 327680 0
1 21 655360 0
2 22 5242880 0
2 23 5242880 1
2 24 5242880 3
2 25 5242880 7
2 26 5242880 15
2 27 5242880 31
2 28 5242880 63
2 29 5242880 127
2 30 5242880 255
2 31 5242880 511
2 32 5242880 1023
2 33 5242880 2047
2 34 5242880 4095
2 35 5242880 8191
2 36 5242880 16383
2 37 5242880 32767
2 38 5242880 65535
2 39 5242880 131071
2 40 5242880 262143
2 41 5242880 524287
3 22 5242880 1
3 24 5242880 3
3 25 5242880 7
3 26 5242880 15
3 27 5242880 31
3 28 5242880 63
3 29 5242880 127
3 30 5242880 255
3 31 5242880 511
3 32 5242880 1023
3 33 5242880 2047
3 34 5242880 4095
3 35 5242880 8191
3 36 5242880 16383
3 37 5242880 32767
3 38 5242880 65535
3 39 5242880 131071
3 40 5242880 262143
3 41 5242880 524287
4 22 5242880 3
4 23 5242880 3
4 25 5242880 7
4 26 5242880 15
4 27 5242880 31
4 28 5242880 63
4 29 5242880 127
4 30 5242880 255
4 31 5242880 511
4 32 5242880 1023
4 33 5242880 2047
4 34 5242880 4095
4 35 5242880 8191
4 36 5242880 16383
4 37 5242880 32767
4 38 5242880 65535
4 39 5242880 131071
4 40 5242880 262143
4 41 5242880 524287
5 22 5242880 7
5 23 5242880 7
5 24 5242880 7
5 26 5242880 15
5 27 5242880 31
5 28 5242880 63
5 29 5242880 127
5 30 5242880 255
5 31 5242880 511
5 32 5242880 1023
5 33 5242880 2047
5 34 5242880 4095
5 35 5242880 8191
5 36 5242880 16383
5 37 5242880 32767
5 38 5242880 65535
5 39 5242880 131071
5 40 5242880 262143
5 41 5242880 524287
6 22 5242880 15
6 23 5242880 15
6 24 5242880 15
6 25 5242880 15
6 27 5242880 31
6 28 5242880 63
6 29 5242880 127
6 30 5242880 255
6 31 5242880 511
6 32 5242880 1023
6 33 5242880 2047
6 34 5242880 4095
6 35 5242880 8191
6 36 5242880 16383
6 37 5242880 32767
6 38 5242880 65535
6 39 5242880 131071
6 40 5242880 262143
6 41 5242880 524287
7 22 5242880 31
7 23 5242880 31
7 24 5242880 31
7 25 5242880 31
7 26 5242880 31
7 28 5242880 63
7 29 5242880 127
7 30 5242880 255
7 31 5242880 511
7 32 5242880 1023
7 33 5242880 2047
7 34 5242880 4095
7 35 5242880 8191
7 36 5242880 16383
7 37 5242880 32767
7 38 5242880 65535
7 39 5242880 131071
7 40 5242880 262143
7 41 5242880 524287
8 22 5242880 63
8 23 5242880 63
8 24 5242880 63
8 25 5242880 63
8 26 5242880 63
8 27 5242880 63
8 29 5242880 127
8 30 5242880 255
8 31 5242880 511
8 32 5242880 1023
8 33 5242880 2047
8 34 5242880 4095
8 35 5242880 8191
8 36 5242880 16383
8 37 5242880 32767
8 38 5242880 65535
8 39 5242880 131071
8 40 5242880 262143
8 41 5242880 524287
9 22 5242880 127
9 23 5242880 127
9 24 5242880 127
9 25 5242880 127
9 26 5242880 127
9 27 5242880 127
9 28 5242880 127
9 30 5242880 255
9 31 5242880 511
9 32 5242880 1023
9 33 5242880 2047
9 34 5242880 4095
9 35 5242880 8191
9 36 5242880 16383
9 37 5242880 32767
9 38 5242880 65535
9 39 5242880 131071
9 40 5242880 262143
9 41 5242880 524287
10 22 5242880 255
10 23 5242880 255
10 24 5242880 255
10 25 5242880 255
10 26 5242880 255
10 27 5242880 255
10 28 5242880 255
10 29 5242880 255
10 31 5242880 511
10 32 5242880 1023
10 33 5242880 2047
10 34 5242880 4095
10 35 5242880 8191
10 36 5242880 16383
10 37 5242880 32767
10 38 5242880 65535
10 39 5242880 131071
10 40 5242880 262143
10 41 5242880 524287
11 22 5242880 511
11 23 5242880 511
11 24 5242880 511
11 25 5242880 511
11 26 5242880 511
11 27 5242880 511
11 28 5242880 511
11 29 5242880 511
11 30 5242880 511
11 32 5242880 1023
11 33 5242880 2047
11 34 5242880 4095
11 35 5242880 8191
11 36 5242880 16383
11 37 5242880 32767
11 38 5242880 65535
11 39 5242880 131071
11 40 5242880 262143
11 41 5242880 524287
12 22 5242880 1023
12 23 5242880 1023
12 24 5242880 1023
12 25 5242880 1023
12 26 5242880 1023
12 27 5242880 1023
12 28 5242880 1023
12 29 5242880 1023
12 30 5242880 1023
12 31 5242880 1023
12 33 5242880 2047
12 34 5242880 4095
12 35 5242880 8191
12 36 5242880 16383
12 37 5242880 32767
12 38 5242880 65535
12 39 5242880 131071
12 40 5242880 262143
12 41 5242880 524287
13 22 5242880 2047
13 23 5242880 2047
13 24 5242880 2047
13 25 5242880 2047
13 26 5242880 2047
13 27 5242880 2047
13 28 5242880 2047
13 29 5242880 2047
13 30 5242880 2047
13 31 5242880 2047
13 32 5242880 2047
13 34 5242880 4095
13 35 5242880 8191
13 36 5242880 16383
13 37 5242880 32767
13 38 5242880 65535
13 39 5242880 131071
13 40 5242880 262143
13 41 5242880 524287
14 22 5242880 4095
14 23 5242880 4095
14 24 5242880 4095
14 25 5242880 4095
14 26 5242880 4095
14 27 5242880 4095
14 28 5242880 4095
14 29 5242880 4095
14 30 5242880 4095
14 31 5242880 4095
14 32 5242880 4095
14 33 5242880 4095
14 35 5242880 8191
14 36 5242880 16383
14 37 5242880 32767
14 38 5242880 65535
14 39 5242880 131071
14 40 5242880 262143
14 41 5242880 524287
15 22 5242880 8191
15 23 5242880 8191
15 24 5242880 8191
15 25 5242880 8191
15 26 5242880 8191
15 27 5242880 8191
15 28 5242880 8191
15 29 5242880 8191
15 30 5242880 8191
15 31 5242880 8191
15 32 5242880 8191
15 33 5242880 8191
15 34 5242880 8191
15 36 5242880 16383
15 37 5242880 32767
15 38 5242880 65535
15 39 5242880 131071
15 40 5242880 262143
15 41 5242880 524287
16 22 5242880 16383
16 23 5242880 16383
16 24 5242880 16383
16 25 5242880 16383
16 26 5242880 16383
16 27 5242880 16383
16 28 5242880 16383
16 29 5242880 16383
16 30 5242880 16383
16 31 5242880 16383
16 32 5242880 16383
16 33 5242880 16383
16 34 5242880 16383
16 35 5242880 16383
16 37 5242880 32767
16 38 5242880 65535
16 39 5242880 131071
16 40 5242880 262143
16 41 5242880 524287
17 22 5242880 32767
17 23 5242880 32767
17 24 5242880 32767
17 25 5242880 32767
17 26 5242880 32767
17 27 5242880 32767
17 28 5242880 32767
17 29 5242880 32767
17 30 5242880 32767
17 31 5242880 32767
17 32 5242880 32767
17 33 5242880 32767
17 34 5242880 32767
17 35 5242880 32767
17 36 5242880 32767
17 38 5242880 65535
17 39 5242880 131071
17 40 5242880 262143
17 41 5242880 524287
18 22 5242880 65535
18 23 5242880 65535
18 24 5242880 65535
18 25 5242880 65535
18 26 5242880 65535
18 27 5242880 65535
18 28 5242880 65535
18 29 5242880 65535
18 30 5242880 65535
18 31 5242880 65535
18 32 5242880 65535
18 33 5242880 65535
18 34 5242880 65535
18 35 5242880 65535
18 36 5242880 65535
18 37 5242880 65535
18 39 5242880 131071
18 40 5242880 262143
18 41 5242880 524287
19 22 5242880 131071
19 23 5242880 131071
19 24 5242880 131071
19 25 5242880 131071
19 26 5242880 131071
19 27 5242880 131071
19 28 5242880 131071
19 29 5242880 131071
19 30 5242880 131071
19 31 5242880 131071
19 32 5242880 131071
19 33 5242880 131071
19 34 5242880 131071
19 35 5242880 131071
19 36 5242880 131071
19 37 5242880 131071
19 38 5242880 131071
19 40 5242880 262143
19 41 5242880 524287
20 22 5242880 262143
20 23 5242880 262143
20 24 5242880 262143
20 25 5242880 262143
20 26 5242880 262143
20 27 5242880 262143
20 28 5242880 262143
20 29 5242880 262143
20 30 5242880 262143
20 31 5242880 262143
20 32 5242880 262143
20 33 5242880 262143
20 34 5242880 262143
20 35 5242880 262143
20 36 5242880 262143
20 37 5242880 262143
20 38 5242880 262143
20 39 5242880 262143
20 41 5242880 524287
21 22 5242880 524287
21 23 5242880 524287
21 24 5242880 524287
21 25 5242880 524287
21 26 5242880 524287
21 27 5242880 524287
21 28 5242880 524287
21 29 5242880 524287
21 30 5242880 524287
21 31 5242880 524287
21 32 5242880 524287
21 33 5242880 524287
21 34 5242880 524287
21 35 5242880 524287
21 36 5242880 524287
21 37 5242880 524287
21 38 5242880 524287
21 39 5242880 524287
21 40 5242880 524287
22 42 2 0
23 42 2 0
24 42 5 0
25 42 10 0
26 42 20 0
27 42 40 0
28 42 80 0
29 42 160 0
30 42 320 0
31 42 640 0
32 42 1280 0
33 42 2560 0
34 42 5120 0
35 42 10240 0
36 42 20480 0
37 42 40960 0
38 42 81920 0
39 42 163840 0
40 42 327680 0
41 42 655360 0

#include <cstdio>
#include "segmenttree.h"

typedef long long ll;

int n, m, p;
std::vector<int> a;

struct Tag
{
    int add, mul;
    Tag(int _add = 0, int _mul = 1) { add = _add; mul = _mul; }
    void operator+=(const Tag& y)
    {
        add = ((ll) add * y.mul + y.add) % p;
        mul = (ll) mul * y.mul % p;
    }
};

int merge(int x, int y)
{
    return (x + y) % p;
}

void update(segmentTreeNode<int, Tag>& node, Tag tag)
{
    node.val = ((ll) node.val * tag.mul + (ll) tag.add * (node.right - node.left)) % p;
    node.tag += tag;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    
    a.resize(n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    
    segmentTree<int, Tag, merge, update> t(n, a, 0);
    
    while (m--)
    {
        int opt, l, r;
        scanf("%d%d%d", &opt, &l, &r);
        if (opt == 1)
        {
            int x;
            scanf("%d", &x);
            t.modify(l, r + 1, Tag(0, x));
        }
        else if (opt == 2)
        {
            int x;
            scanf("%d", &x);
            t.modify(l, r + 1, Tag(x, 1));
        }
        else printf("%d\n", t.query(l, r + 1));
    }
    
    return 0;
}

Let $$$lim(u, i)$$$ be $$$\min_{r(v)\ge i}dis(u, v)$$$, enumerate each node $$$u$$$ ordered by $$$r_u$$$ decreasingly, use Dijkstra to calc the shortest path from $$$u$$$, push $$$v$$$ into the heap/priority_queue used for Dijkstra only when $$$dis(u,v)<lim(v,r(u)+1)$$$, when a new node is pushed into the heap/priority_queue, add answer by one.

#include <iostream>
#include <cstdio>
#include <queue>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

int read()
{
	int out = 0;
	char c;
	while (!isdigit(c = getchar()));
	for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
	return out;
}

const int R = 12;
const int N = 30010;
const int M = 150010;

int head[N], to[M << 1], nxt[M << 1], edge[M << 1], cnt;
priority_queue<pii, vector<pii>, greater<pii> > q;
int n, m, r[N], lim[N][R], dis[N], vis[N], ans;

void add(int u, int v, int w)
{
	nxt[++cnt] = head[u];
	head[u] = cnt;
	to[cnt] = v;
	edge[cnt] = w;
}

int main()
{
	n = read();
	m = read();
	
	for (int i = 1; i <= n; ++i) r[i] = read();
	
	for (int i = 1; i <= m; ++i)
	{
		int u = read();
		int v = read();
		int w = read();
		add(u, v, w);
		add(v, u, w);
	}
	
	memset(lim, 0x3f, sizeof(lim));
	
	ans = n;
	
	for (int s = 10; s >= 1; --s)
	{
		for (int i = 1; i <= n; ++i) lim[i][s] = lim[i][s + 1];
		for (int t = 1; t <= n; ++t)
		{
			if (r[t] != s) continue;
			dis[t] = 0;
			vis[t] = t;
			lim[t][s] = 0;
			q.push(pii(0, t));
			
			while (!q.empty())
			{
				int u = q.top().second;
				int d = q.top().first;
				q.pop();
				if (d > dis[u]) continue;
				for (int i = head[u]; i; i = nxt[i])
				{
					int v = to[i];
					int w = edge[i];
					if ((vis[v] != t || dis[v] > d + w) && (d + w < lim[v][s + 1]))
					{
						if (vis[v] != t) ++ans;
						vis[v] = t;
						dis[v] = d + w;
						lim[v][s] = min(lim[v][s], dis[v]);
						q.push(pii(d + w, v));
					}
				}
			}
		}
	}
	
	cout << ans;
	
	return 0;
}

Let $$$x=pyz + qy+r$$$, where $$$0\le q<z$$$ and $$$0\le r<y$$$.

Then, $$$\left\lfloor\frac{x}{y}\right\rfloor=pz+q$$$, and $$$\left\lfloor\frac{pz+q}{z}\right\rfloor=p$$$, which is equal to $$$\left\lfloor\frac{x}{yz}\right\rfloor$$$.

The answer is $$$size[x]\cdot size[y]$$$, you can makeroot(x), access(y), Splay(y), then print (t[x].vir + 1) * (t[y].vir + 1).

#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100010;

struct Node
{
    int ch[2], fa, vir, siz;
    bool rev;
} t[N];

bool nroot(int x);
void rotate(int x);
void Splay(int x);
void access(int x);
void makeroot(int x);
void split(int x, int y);
void link(int x, int y);
void reverse(int x);
void pushup(int x);
void pushdown(int x);

int n, q, sta[N], top;

int main()
{
    int x, y;
    char op[10];

    scanf("%d%d", &n, &q);

    while (q--)
    {
        scanf("%s%d%d", op, &x, &y);
        if (op[0] == 'A') link(x, y);
        else
        {
            split(x, y);
            printf("%lld\n", 1ll * (t[x].vir + 1) * (t[y].vir + 1));
        }
    }

    return 0;
}

bool nroot(int x) { return x == t[t[x].fa].ch[0] || x == t[t[x].fa].ch[1]; }

void rotate(int x)
{
    int y = t[x].fa;
    int z = t[y].fa;
    int k = x == t[y].ch[1];
    if (nroot(y)) t[z].ch[y == t[z].ch[1]] = x;
    t[x].fa = z;
    t[y].ch[k] = t[x].ch[k ^ 1];
    t[t[x].ch[k ^ 1]].fa = y;
    t[x].ch[k ^ 1] = y;
    t[y].fa = x;
    pushup(y);
    pushup(x);
}

void Splay(int x)
{
    int u = x;
    sta[++top] = x;
    while (nroot(u)) sta[++top] = u = t[u].fa;
    while (top) pushdown(sta[top--]);
    while (nroot(x))
    {
        int y = t[x].fa;
        int z = t[y].fa;
        if (nroot(y)) (x == t[y].ch[1]) ^ (y == t[z].ch[1]) ? rotate(x) : rotate(y);
        rotate(x);
    }
}

void access(int x)
{
    for (int y = 0; x; x = t[y = x].fa)
    {
        Splay(x);
        t[x].vir += t[t[x].ch[1]].siz;
        t[x].ch[1] = y;
        t[x].vir -= t[t[x].ch[1]].siz;
        pushup(x);
    }
}

void makeroot(int x)
{
    access(x);
    Splay(x);
    reverse(x);
}

void split(int x, int y)
{
    makeroot(x);
    access(y);
    Splay(y);
}

void link(int x, int y)
{
    makeroot(x);
    access(y);
    Splay(y);
    t[x].fa = y;
    t[y].vir += t[x].siz;
}

void reverse(int x)
{
    swap(t[x].ch[0], t[x].ch[1]);
    t[x].rev ^= 1;
}

void pushup(int x)
{
    t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + t[x].vir + 1;
}

void pushdown(int x)
{
    if (t[x].rev)
    {
        reverse(t[x].ch[0]);
        reverse(t[x].ch[1]);
        t[x].rev = false;
    }
}

Give each node a weight, let the "sum" of subtrees be the XOR sum.

When inserting a new simple path, generate a random number (a big one, in a range about $$$2^{64}$$$), then let $$$u$$$'s and $$$v$$$'s weights be XORed by the random number. We call the random number "the weight of the simple path".

Why do we use XOR? Because if two endpoints of a simple path are in the same subtree, their XOR sum will be zero.

Thus, when answering the query, calculate the XOR sum of subtrees $$$x$$$ and $$$y$$$, if they are both equal to the XOR sum of all weights of the simple paths in $$$S$$$, the answer is very likely to be "YES".

When deleting a simple path, you just need to let $$$u$$$'s and $$$v$$$'s weights be XORed by the weight of the simple path again, also the total XOR sum of $$$S$$$ will be XORed by the weight of the simple path.

Maintaining XOR sum using LCT is just like maintaining the size.

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <ctime>
#include <iostream>

using namespace std;

int read()
{
    int out = 0;
    char c;
    while (!isdigit(c = getchar()));
    for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
    return out;
}

typedef unsigned long long ull;

const int N = 100010;
const int M = 300010;

ull seed = time(0);
ull rd() { return seed = seed * 998244353 + 1000000007; }

struct Node
{
    int ch[2], fa;
    ull self, val, vir;
    bool rev;
} t[N];

bool nroot(int x);
void rotate(int x);
void Splay(int x);
void access(int x);
void makeroot(int x);
void link(int x, int y);
void cut(int x, int y);
void reverse(int x);
void pushup(int x);
void pushdown(int x);

int id, n, m, sta[N], top, sx[M], sy[M], stot;
ull xorp[M], xorsum;

int main()
{
    int i, x, y;

    id = read();
    n = read();
    m = read();

    for (i = 1; i < n; ++i) link(read(), read());

    while (m--)
    {
        switch (read())
        {
            case 1:
                cut(read(), read());
                link(read(), read());
                break;
            case 2:
                sx[++stot] = x = read();
                sy[stot] = y = read();
                xorp[stot] = rd();
                access(x);
                Splay(x);
                t[x].self ^= xorp[stot];
                access(y);
                Splay(y);
                t[y].self ^= xorp[stot];
                xorsum ^= xorp[stot];
                break;
            case 3:
                x = read();
                access(sx[x]);
                Splay(sx[x]);
                t[sx[x]].self ^= xorp[x];
                access(sy[x]);
                Splay(sy[x]);
                t[sy[x]].self ^= xorp[x];
                xorsum ^= xorp[x];
                break;
            case 4:
                x = read();
                y = read();
                makeroot(x);
                access(y);
                if ((t[y].vir ^ t[y].self) == xorsum) puts("YES");
                else puts("NO");
                break;
        }
    }

    return 0;
}

bool nroot(int x) { return x == t[t[x].fa].ch[0] || x == t[t[x].fa].ch[1]; }

void rotate(int x)
{
    int y = t[x].fa;
    int z = t[y].fa;
    int k = x == t[y].ch[1];
    if (nroot(y)) t[z].ch[y == t[z].ch[1]] = x;
    t[x].fa = z;
    t[y].ch[k] = t[x].ch[k ^ 1];
    t[t[x].ch[k ^ 1]].fa = y;
    t[x].ch[k ^ 1] = y;
    t[y].fa = x;
    pushup(y);
    pushup(x);
}

void Splay(int x)
{
    int u = x;
    sta[++top] = u;
    while (nroot(u)) sta[++top] = u = t[u].fa;
    while (top) pushdown(sta[top--]);
    while (nroot(x))
    {
        int y = t[x].fa;
        int z = t[y].fa;
        if (nroot(y)) (x == t[y].ch[1]) ^ (y == t[z].ch[1]) ? rotate(x) : rotate(y);
        rotate(x);
    }
}

void access(int x)
{
    for (int y = 0; x; x = t[y = x].fa)
    {
        Splay(x);
        t[x].vir ^= t[t[x].ch[1]].val;
        t[x].vir ^= t[t[x].ch[1] = y].val;
        pushup(x);
    }
}

void makeroot(int x)
{
    access(x);
    Splay(x);
    reverse(x);
}

void link(int x, int y)
{
    makeroot(x);
    access(y);
    Splay(y);
    t[x].fa = y;
    t[y].vir ^= t[x].val;
}

void cut(int x, int y)
{
    makeroot(x);
    access(y);
    Splay(y);
    t[x].fa = t[y].ch[0] = 0;
    pushup(y);
}

void reverse(int x)
{
    swap(t[x].ch[0], t[x].ch[1]);
    t[x].rev ^= 1;
}

void pushup(int x)
{
    t[x].val = t[x].self ^ t[x].vir ^ t[t[x].ch[0]].val ^ t[t[x].ch[1]].val;
}

void pushdown(int x)
{
    if (t[x].rev)
    {
        reverse(t[x].ch[0]);
        reverse(t[x].ch[1]);
        t[x].rev = false;
    }
}

Consider the two edge cases: all the $$$z$$$ persons upvote / all the $$$z$$$ persons downvote. If the results are the same in these two cases, it is the answer. Otherwise, the result is uncertain.

#include <iostream>

using namespace std;

const char result[4] = {'+', '-', '0', '?'};

int solve(int x, int y)
{
	return x == y ? 2 : x < y;
}

int main()
{
	int x, y, z;
	
	cin >> x >> y >> z;
	
	cout << result[solve(x + z, y) == solve(x, y + z) ? solve(x, y) : 3];
	
	return 0;
}

• $$$m\ge\left\lfloor\frac n 2\right\rfloor+1$$$

Consider the chess pieces $$$1$$$ and $$$n$$$.

$$$\because\begin{cases}|r_1-r_n|+|c_1-c_n|\ge n-1\\|r_1-r_n|\le m-1\\|c_1-c_n|\le m-1\end{cases}$$$

$$$\therefore m-1+m-1\ge n-1$$$

$$$\therefore m\ge\frac{n+1}2$$$

$$$\because m\text{ is an integer}$$$

$$$\therefore m\ge\left\lfloor\frac n 2\right\rfloor+1$$$

• $$$m$$$ can be $$$\left\lfloor\frac n 2\right\rfloor+1$$$

If we put the $$$i$$$-th piece on $$$(r_i,c_i)$$$ satisfying $$$r_i+c_i=i+1$$$, it is a feasible plan, because $$$|r_i-r_j|+|c_i-c_j|\ge|r_i+c_i-r_j-c_j|$$$.

#include <cstdio>

using namespace std;

int main()
{
    int n, i, ans;

    scanf("%d", &n);
    ans = n / 2 + 1;

    printf("%d", ans);

    for (i = 1; i <= ans; ++i) printf("\n%d 1", i);
    for (i = 2; i <= n - ans + 1; ++i) printf("\n%d %d", ans, i);

    return 0;
}

First, try to finish it without playing any empty cards.

If that's not possible, the best choice is to play several empty cards in a row, then play from $$$1$$$ to $$$n$$$. For a card $$$i$$$, suppose that it is in the $$$p_i$$$-th position in the pile ($$$p_i=0$$$ if it is in the hand), you have to play at least $$$p_i - i + 1$$$ empty cards. So the answer will be $$$\max\{p_i-i+1+n\}$$$.

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, a[N], b[N], p[N], ans;

int main()
{
    int i, j;

    scanf("%d", &n);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
        p[a[i]] = 0;
    }

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", b + i);
        p[b[i]] = i;
    }

    if (p[1])
    {
        for (i = 2; p[i] == p[1] + i - 1; ++i);
        if (p[i - 1] == n)
        {
            for (j = i; j <= n && p[j] <= j - i; ++j);
            if (j > n)
            {
                printf("%d", n - i + 1);
                return 0;
            }
        }
    }

    for (i = 1; i <= n; ++i) ans = max(ans, p[i] - i + 1 + n);

    printf("%d", ans);

    return 0;
}

First, if we choose a node as the root, then each subtree must be in a continuous arc on the circle. Then, we can use DP to solve this problem.

Let $$$f_u$$$ be the number of plans to draw the subtree of $$$u$$$, then $$$f_u=(|son(u)|+[u\ne root])!\prod\limits_{v\in son(u)}f_v$$$ — choose a position for each subtree and then $$$u$$$ itself, then draw the subtrees. However, instead of choosing the position of the root, we suppose the root is on a certain point on the circle, then rotate the circle, thus get the answer: $$$nf_{root}$$$.

In fact, we don't have to write a DP, the answer is $$$n$$$ times the product of the factorial of each node's degree ($$$n\prod\limits_{i = 1}^ndegree[i]!$$$).

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 200010;
const int mod = 998244353;

int n, ans, d[N];

int main()
{
    int i, u, v;

    scanf("%d", &n);
    ans = n;

    for (i = 1; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        ans = (ll) ans * (++d[u]) % mod * (++d[v]) % mod;
    }

    cout << ans;

    return 0;
}

First, let's focus on a single picture with weight $$$w$$$ which Nauuo likes, so we only have to know the sum of the weights of the pictures Nauuo likes ($$$SA=\sum\limits_{i=1}^nw_i[a_i=1]$$$) and the sum of the disliked ones ($$$SB=\sum\limits_{i=1}^nw_i[a_i=0]$$$) instead of all the $$$n$$$ weights.

Then, we can use DP to solve this problem.

Let $$$f_w[i][j][k]$$$ be the expected weight of a picture Nauuo likes with weight $$$w$$$ after another $$$i$$$ visits since $$$SA=j$$$ and $$$SB=k$$$.

Obviously, $$$f_w[0][j][k]=w$$$.

The state transition:

• The next visit displays the picture we focus on. Probaility: $$$\frac w{j+k}$$$. Lead to: $$$f_{w+1}[i-1][j+1][k]$$$.

• The next visit displays a picture Nauuo likes but is not the one we focus on. Probaility: $$$\frac{j-w}{j+k}$$$. Lead to: $$$f_w[i-1][j+1][k]$$$.

• The next visit displays a picture Nauuo doesn't like. Probaility: $$$\frac k{j+k}$$$. Lead to: $$$f_w[i-1][j][k-1]$$$.

So, $$$f_w[i][j][k]=\frac w{j+k}f_{w+1}[i-1][j+1][k]+\frac{j-w}{j+k}f_w[i-1][j+1][k]+\frac k{j+k}f_w[i-1][j][k-1]$$$.

Let $$$g_w[i][j][k]$$$ be the expected weight of a picture Nauuo doesn't like with weight $$$w$$$ after another $$$i$$$ visits since $$$SA=j$$$ and $$$SB=k$$$. The state transition is similar.

Note that $$$i,\,j,\,k,\,m$$$ have some relation. In fact we can let $$$f'_w[i][j]$$$ be $$$f_w[m-i-j][SA+i][SB-j]$$$ ($$$SA$$$ and $$$SB$$$ are the initial ones here).

But up to now, we can only solve the easy version.

To solve the hard version, let's introduce a lemma:

Proof:

Obviously, this is true when $$$i=0$$$.

Then, suppose we have already proved $$$f_w[i-1][j][k]=wf_1[i-1][j][k]$$$.

$$$\begin{aligned}f_1[i][j][k]&=\frac 1{j+k}f_2[i-1][j+1][k]+\frac{j-1}{j+k}f_1[i-1][j+1][k]+\frac k{j+k}f_1[i-1][j][k-1]\\&=\frac2{j+k}f_1[i-1][j+1][k]+\frac{j-1}{j+k}f_1[i-1][j+1][k]+\frac k{j+k}f_1[i-1][j][k-1]\\&=\frac{j+1}{j+k}f_1[i-1][j+1][k]+\frac k{j+k}f_1[i-1][j][k-1]\end{aligned}$$$

$$$\begin{aligned}f_w[i][j][k]&=\frac w{j+k}f_{w+1}[i-1][j+1][k]+\frac{j-w}{j+k}f_w[i-1][j+1][k]+\frac k{j+k}f_w[i-1][j][k-1]\\&=\frac{w(w+1)}{j+k}f_1[i-1][j+1][k]+\frac{w(j-w)}{j+k}f_1[i-1][j+1][k]+\frac {wk}{j+k}f_1[i-1][j][k-1]\\&=\frac{w(j+1)}{j+k}f_1[i-1][j+1][k]+\frac {wk}{j+k}f_1[i-1][j][k-1]\\&=wf_1[i][j][k]\end{aligned}$$$

Also, a brief but not so strict proof: the increment in each step is proportional to the expectation.

So, we only have to calculate $$$f_1[i][j][k]$$$ ($$$f'_1[i][j]$$$).

In conclusion:

$$$f'_1[i][j]=1\ (i+j=m)$$$

$$$f'_1[i][j]=\frac{SA+i+1}{SA+SB+i-j}f'_1[i+1][j]+\frac{SB-j}{SA+SB+i-j}f'_1[i][j+1]\ (i+j<m)$$$

$$$g'_1[i][j]=1\ (i+j=m)$$$

$$$g'_1[i][j]=\frac{SA+i}{SA+SB+i-j}g'_1[i+1][j]+\frac{SB-j-1}{SA+SB+i-j}g'_1[i][j+1]\ (i+j<m)$$$

If $$$a_i=1$$$, the expected weight of the $$$i$$$-th picture is $$$w_if'_1[0][0]$$$, otherwise, the expected weight is $$$w_ig'_1[0][0]$$$.

Last question: how to calculate the result modulo $$$998244353$$$?

If you don't know how, please read the wiki to learn it.

You can calculate and store all the $$$\mathcal O(m)$$$ inverses at first, then you can get an $$$\mathcal O(n+m^2+m\log p)$$$ solution instead of $$$\mathcal O(n+m^2\log p)$$$ ($$$p=998244353$$$ here).

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 200010;
const int M = 3010;
const int mod = 998244353;

int qpow(int x, int y) //calculate the modular multiplicative inverse
{
	int out = 1;
	while (y)
	{
		if (y & 1) out = (ll) out * x % mod;
		x = (ll) x * x % mod;
		y >>= 1;
	}
	return out;
}

int n, m, a[N], w[N], f[M][M], g[M][M], inv[M << 1], sum[3];

int main()
{
	int i,j;
	
	scanf("%d%d", &n, &m);
	
	for (i = 1; i <= n; ++i) scanf("%d", a + i);
	
	for (i = 1; i <= n; ++i)
	{
		scanf("%d", w + i);
		sum[a[i]] += w[i];
		sum[2] += w[i];
	}
	
	for (i = max(0, m - sum[0]); i <= 2 * m; ++i) inv[i] = qpow(sum[2] + i - m, mod - 2);
	
	for (i = m; i >= 0; --i)
	{
		f[i][m - i] = g[i][m - i] = 1;
		for (j = min(m - i - 1, sum[0]); j >= 0; --j)
		{
			f[i][j] = ((ll) (sum[1] + i + 1) * f[i + 1][j] + (ll) (sum[0] - j) * f[i][j + 1]) % mod * inv[i - j + m] % mod;
			g[i][j] = ((ll) (sum[1] + i) * g[i + 1][j] + (ll) (sum[0] - j - 1) * g[i][j + 1]) % mod * inv[i - j + m] % mod;
		}
	}
	
	for (i = 1; i <= n; ++i) printf("%d\n", int((ll) w[i] * (a[i] ? f[0][0] : g[0][0]) % mod));
	
	return 0;
}

Consider this problem:

the person in $$$(i,1)$$$ facing right is numbered $$$a_i$$$, the person in $$$(1,i)$$$ facing bottom is numbered $$$b_i$$$. The person numbered $$$p_i$$$ has to exit the grid from $$$(i,n)$$$, the person numbered $$$q_i$$$ has to exit the grid from $$$(n,i)$$$.

The original problem can be easily transferred to this problem. And now let's transfer it into an $$$(n-1)\times (n-1)$$$ subproblem by satisfying the requirement of the first row and the first column.

If $$$a_1=p_1$$$ and $$$b_1=q_1$$$, you can simply do nothing and get an $$$(n-1)\times (n-1)$$$ subproblem.

Otherwise, you can set a portal consisting of two doors in $$$(x,1)$$$ and $$$(1,y)$$$ where $$$a_x=p_1$$$ and $$$b_y=q_1$$$. Swap $$$a_1$$$ and $$$a_x$$$, $$$b_1$$$ and $$$b_y$$$, then you will get an $$$(n-1)\times(n-1)$$$ subproblem.

Then, you can solve the problem until it changes into a $$$1\times1$$$ one.

This problem can be solved in $$$\mathcal O(n)$$$, but the checker needs $$$\mathcal O(n^2)$$$.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1010;

struct Portal
{
	int x, y, p, q;
	Portal(int _x, int _y, int _p, int _q): x(_x), y(_y), p(_p), q(_q) {}
};
vector<Portal> ans;
int n, a[N], b[N], c[N], d[N], ra[N], rb[N], rc[N], rd[N];

int main()
{
	int i;
	
	scanf("%d", &n);
	
	for (i = 1; i <= n; ++i)
	{
		scanf("%d", b + i);
		rb[b[i]] = i;
	}
	for (i = 1; i <= n; ++i)
	{
		scanf("%d", a + i);
		ra[a[i]] = i;
	}
	for (i = 1; i <= n; ++i) c[i] = d[i] = rc[i] = rd[i] = i;
	
	for (i = 1; i < n; ++i)
	{
		if (c[i] == ra[i] && d[i] == rb[i]) continue;
		ans.push_back(Portal(i, rc[ra[i]], rd[rb[i]], i));
		int t1 = c[i];
		int t2 = d[i];
		swap(c[i], c[rc[ra[i]]]);
		swap(d[i], d[rd[rb[i]]]);
		swap(rc[ra[i]], rc[t1]);
		swap(rd[rb[i]], rd[t2]);
	}
	
	printf("%d\n", ans.size());
	for (auto k : ans) printf("%d %d %d %d\n", k.x, k.y, k.p, k.q);
	
	return 0;
}

For each color, we can try to maintain the number of simple paths that do not contain such color.

If we can maintain such information, we can easily calculate the number of simple paths that contain a certain color, thus get the answer.

For each color, we delete all nodes that belong to such color, thus splitting the tree into some clusters (here we define a "cluster" as a connected subgraph of the original tree).

By maintaining $$$\sum\text{cluster size}^2$$$, we can get the number of simple paths that do not contain such color.

For each color we try to maintain the same information, add them together, and get the answer.

So now the problem is: a white tree

1. reverse the color of a node ( white <-> black )

2. output $$$\sum\text{cluster size}^2$$$

This problem can be solved by many data structures like top tree, link/cut tree or heavy path decomposition.

Let's use the link/cut tree for example.

You can maintain the size of each subtree and the sum of $$$\text{size}^2$$$ of each node's sons. Link/cut one node with its father (choose a node as the root and make the tree a rooted-tree first) when its color changes. In this way, the real clusters are the ones that are still connected after deleting the top node of a cluster in the link/cut tree. Update $$$\sum\text{cluster size}^2$$$ while linking/cutting.

link:

cut:

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 400010;

struct Node
{
    int fa, ch[2], siz, sizi;
    ll siz2i;
    ll siz2() { return (ll) siz * siz; }
} t[N];

bool nroot(int x);
void rotate(int x);
void Splay(int x);
void access(int x);
int findroot(int x);
void link(int x);
void cut(int x);
void pushup(int x);

void add(int u, int v);
void dfs(int u);

int head[N], nxt[N << 1], to[N << 1], cnt;
int n, m, c[N], f[N];
ll ans, delta[N];
bool bw[N];
vector<int> mod[N][2];

int main()
{
    int i, j, u, v;
    ll last;

    scanf("%d%d", &n, &m);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d", c + i);
        mod[c[i]][0].push_back(i);
        mod[c[i]][1].push_back(0);
    }

    for (i = 1; i <= n + 1; ++i) t[i].siz = 1;

    for (i = 1; i < n; ++i)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }

    for (i = 1; i <= m; ++i)
    {
        scanf("%d%d", &u, &v);
        mod[c[u]][0].push_back(u);
        mod[c[u]][1].push_back(i);
        c[u] = v;
        mod[v][0].push_back(u);
        mod[v][1].push_back(i);
    }

    f[1] = n + 1;
    dfs(1);

    for (i = 1; i <= n; ++i) link(i);

    for (i = 1; i <= n; ++i)
    {
        if (!mod[i][0].size())
        {
            delta[0] += (ll)n * n;
            continue;
        }
        if (mod[i][1][0])
        {
            delta[0] += (ll)n * n;
            last = (ll)n * n;
        } else
            last = 0;
        for (j = 0; j < mod[i][0].size(); ++j)
        {
            u = mod[i][0][j];
            if (bw[u] ^= 1)
                cut(u);
            else
                link(u);
            if (j == mod[i][0].size() - 1 || mod[i][1][j + 1] != mod[i][1][j])
            {
                delta[mod[i][1][j]] += ans - last;
                last = ans;
            }
        }
        for (j = mod[i][0].size() - 1; ~j; --j)
        {
            u = mod[i][0][j];
            if (bw[u] ^= 1)
                cut(u);
            else
                link(u);
        }
    }

    ans = (ll) n * n * n;
    for (i = 0; i <= m; ++i)
    {
        ans -= delta[i];
        printf("%I64d ", ans);
    }

    return 0;
}

bool nroot(int x) { return x == t[t[x].fa].ch[0] || x == t[t[x].fa].ch[1]; }

void rotate(int x)
{
    int y = t[x].fa;
    int z = t[y].fa;
    int k = x == t[y].ch[1];
    if (nroot(y)) t[z].ch[y == t[z].ch[1]] = x;
    t[x].fa = z;
    t[y].ch[k] = t[x].ch[k ^ 1];
    t[t[x].ch[k ^ 1]].fa = y;
    t[x].ch[k ^ 1] = y;
    t[y].fa = x;
    pushup(y);
    pushup(x);
}

void Splay(int x)
{
    while (nroot(x))
    {
        int y = t[x].fa;
        int z = t[y].fa;
        if (nroot(y)) (x == t[y].ch[1]) ^ (y == t[z].ch[1]) ? rotate(x) : rotate(y);
        rotate(x);
    }
}

void access(int x)
{
    for (int y = 0; x; x = t[y = x].fa)
    {
        Splay(x);
        t[x].sizi += t[t[x].ch[1]].siz;
        t[x].sizi -= t[y].siz;
        t[x].siz2i += t[t[x].ch[1]].siz2();
        t[x].siz2i -= t[y].siz2();
        t[x].ch[1] = y;
        pushup(x);
    }
}

int findroot(int x)
{
    access(x);
    Splay(x);
    while (t[x].ch[0]) x = t[x].ch[0];
    Splay(x);
    return x;
}

void link(int x)
{
    int y = f[x];
    Splay(x);
    ans -= t[x].siz2i + t[t[x].ch[1]].siz2();
    int z = findroot(y);
    access(x);
    Splay(z);
    ans -= t[t[z].ch[1]].siz2();
    t[x].fa = y;
    Splay(y);
    t[y].sizi += t[x].siz;
    t[y].siz2i += t[x].siz2();
    pushup(y);
    access(x);
    Splay(z);
    ans += t[t[z].ch[1]].siz2();
}

void cut(int x)
{
    int y = f[x];
    access(x);
    ans += t[x].siz2i;
    int z = findroot(y);
    access(x);
    Splay(z);
    ans -= t[t[z].ch[1]].siz2();
    Splay(x);
    t[x].ch[0] = t[t[x].ch[0]].fa = 0;
    pushup(x);
    Splay(z);
    ans += t[t[z].ch[1]].siz2();
}

void pushup(int x)
{
    t[x].siz = t[t[x].ch[0]].siz + t[t[x].ch[1]].siz + t[x].sizi + 1;
}

void add(int u, int v)
{
    nxt[++cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
}

void dfs(int u)
{
    int i, v;
    for (i = head[u]; i; i = nxt[i])
    {
        v = to[i];
        if (v != f[u])
        {
            f[v] = u;
            dfs(v);
        }
    }
}

At first, let's solve this problem in $$$\mathcal{O}(n\sqrt{n \log n})$$$.

Let's split our array into blocks by $$$B$$$ integers, and let's find a function, $$$f(x) = $$$ which value you will get at the end of the current block if you will start with $$$x$$$. With simple induction, you can prove that this function is a piece-wise linear, and it has $$$\mathcal{O}(B)$$$ segments, so you can build it iteratively in $$$\mathcal{O}(B^2)$$$ time for each block, so the preprocessing took $$$\mathcal{O}(nB)$$$.

And to answer the query, you can keep the current value of $$$x$$$ and then find with binary search by that piece-wise linear function the $$$f(x)$$$ for the current block.

With a good choice of $$$B$$$, this solution will work in $$$\mathcal{O}(n\sqrt{n \log n})$$$.

Ok, but then how to solve it in $$$\mathcal{O}(n \log + q \log^2)$$$?

Lemma: each segment of this piece-wise linear function has length at least $$$p$$$.

You can prove it with simple induction.

And then, with this lemma, it is possible by two functions $$$f(x)$$$ of size $$$n$$$ and $$$g(x)$$$ of size $$$m$$$ find the new function $$$h(x) = g(f(x))$$$, in the $$$\mathcal{O}(n + m)$$$, you can do it with two pointers, similar to the previous iterative method, but adding a several points to the function each time, best way to understand it is to check the indendent solution :)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1000005;
const ll inf = (ll)1e16;
int n, m, P, a[N];
ll sum[N];
vector<ll> func[N << 2];

vector<ll> merge(int l, int r, int mid, const vector<ll> &f, const vector<ll> &g) {
	ll suml = sum[mid] - sum[l - 1], sumr = sum[r] - sum[mid];
	vector<ll> ret(f.size() + g.size() - 1, inf);
	for (int i = 0, j = 0; i < (int)f.size(); ++i) {
		ll xl = f[i], xr = (i + 1 == (int)f.size() ? inf : f[i + 1] - 1), yl = xl + suml - (ll)i * P, yr = xr + suml - (ll)i * P;
		while (j > 0 && g[j] > yl) --j;
		while (j < (int)g.size() && (j == 0 || g[j] <= yl)) ++j;
		--j;
		for (; j < (int)g.size() && g[j] <= yr; ++j)
			ret[i + j] = min(ret[i + j], max(xl, g[j] - suml + (ll)i * P));
	}
	ret[0] = -inf;
	return ret;
}
void build(int u, int l, int r) {
	if (l == r) {
		func[u].push_back(-inf);
		func[u].push_back(P - a[l]);
		return;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	func[u] = merge(l, r, mid, func[u << 1], func[u << 1 | 1]);
}
ll query(int u, int l, int r, int ql, int qr, ll now) {
	if (l >= ql && r <= qr)
		return now + sum[r] - sum[l - 1] - (ll)P * (upper_bound(func[u].begin(), func[u].end(), now) - func[u].begin() - 1);
	int mid = l + r >> 1;
	if (qr <= mid)
		return query(u << 1, l, mid, ql, qr, now);
	if (ql > mid)
		return query(u << 1 | 1, mid + 1, r, ql, qr, now);
	return query(u << 1 | 1, mid + 1, r, ql, qr, query(u << 1, l, mid, ql, qr, now));
}

int main() {
	scanf("%d%d%d", &n, &m, &P);
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i), sum[i] = sum[i - 1] + a[i];
	build(1, 1, n);
	for (int l, r; m--;) {
		scanf("%d%d", &l, &r);
		printf("%I64d\n", query(1, 1, n, l, r, 0));
	}
	return 0;
}