@yang12138
2023-05-12T10:31:12.000000Z
字数 63810
阅读 556
未分类
#include <bits/stdc++.h>
using namespace std;
class KMP {
private:
static const int LEN = 100000 + 10;
static int next[LEN];
template<class T>
static void GetNext(const T* const s, int n) {
next[0] = -1;
for (int i = 1; i < n; i++) {
next[i] = next[i-1];
while (next[i] >= 0 && s[next[i]+1] != s[i]) next[i] = next[next[i]];
if (s[next[i]+1] == s[i]) next[i]++;
}
}
public:
// match t on s
template<class T>
static int Gao(const T* const s, int n, const T* const t, int m) {
GetNext(t, m);
int pos = -1, ans = 0;
for (int i = 0; i < n; i++) {
while (pos >= 0 && s[i] != t[pos+1]) pos = next[pos];
if (s[i] == t[pos+1]) pos++;
if (pos == m-1) return i - m + 1;
}
return -2;
}
};
int KMP::next[KMP::LEN];
int a[1000010], b[10010];
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
assert(n <= 100000);
for (int i = 0; i < n; i++) scanf("%d", a+i);
for (int i = 0; i < m; i++) scanf("%d", b+i);
printf("%d\n", KMP::Gao(a, n, b, m)+1);
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class Manacher {
public:
static int Gao(const char* const str, int n) {
int m = 0;
t[m++] = '!';
for (int i = 0; i < n; i++) {
t[m++] = '@';
t[m++] = str[i];
}
t[m++] = '@';
int center = 0, radius = 0;
ll ans = 0;
int len = 0;
for (int i = 0; i < m; i++) {
if (i < center + radius)
r[i] = min(r[2 * center - i], center + radius - i);
while (t[i - r[i] - 1] == t[i + r[i] + 1]) r[i]++;
if (i + r[i] > center + radius) center = i, radius = r[i];
ans += (r[i] + 1) / 2;
len = max(len, r[i]);
}
// return ans;
return len;
}
private:
static const int LEN = 2000000 + 10;
static char t[LEN];
static int r[LEN];
};
char Manacher::t[Manacher::LEN];
int Manacher::r[Manacher::LEN];
char in[800010];
int main() {
scanf("%s", in);
printf("%d\n", Manacher::Gao(in, strlen(in)));
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SA {
static const int N = 1e5 + 10;
// a_i >= 0
void GetSA(const int* a, int n) {
int up = 0;
for (int i = 0; i < n; i++) up = max(up, a[i]);
up++;
int *rk1 = rk[0], *rk2 = rk[1];
std::fill(cnt, cnt + up, 0);
for (int i = 0; i < n; i++) cnt[rk1[i] = a[i]]++;
for (int i = 0; i+1 < up; i++) cnt[i+1] += cnt[i];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk1[i]]] = i;
for (int d = 1; d <= n; d <<= 1) {
int p = 0;
for (int i = n - d; i < n; i++) id[p++] = i;
for (int i = 0; i < n; i++) if (sa[i] >= d) id[p++] = sa[i] - d;
std::fill(cnt, cnt + up, 0);
for (int i = 0; i < n; i++) cnt[rk2[i] = rk1[id[i]]]++;
for (int i = 0; i+1 < up; i++) cnt[i+1] += cnt[i];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk2[i]]] = id[i];
rk2[sa[0]] = 0;
for (int i = 1; i < n; i++) {
if (sa[i-1] + d < n && sa[i] + d < n && rk1[sa[i-1]] == rk1[sa[i]]
&& rk1[sa[i-1]+d] == rk1[sa[i]+d])
rk2[sa[i]] = rk2[sa[i-1]];
else rk2[sa[i]] = rk2[sa[i-1]] + 1;
}
swap(rk1, rk2);
up = n;
if (rk2[sa[n-1]] == n) break;
}
height[0] = 0;
for (int i = 0, p = 0; i < n; i++) {
if (rk1[i] == 0) continue;
int j = sa[rk1[i]-1];
while (i + p < n && j + p < n && a[i+p] == a[j+p]) p++;
height[rk1[i]] = p;
p = max(0, p-1);
}
}
void GetSA(const char* s) {
int n = strlen(s);
int* a = new int[n];
for (int i = 0; i < n; i++) a[i] = s[i];
GetSA(a, n);
}
int cnt[N], id[N];
int sa[N]; // index from 0 ~ n-1
int rk[2][N]; // index from 0 ~ n-1
int height[N]; // index from 1 ~ n-1, largest common prefix of suffix_sa[i] and suffix_sa[i-1]
} sagetter;
void solve() {
string s;
cin >> s;
sagetter.GetSA(s.c_str());
int* sa = sagetter.sa;
int* h = sagetter.height;
for (int i = 0; i < s.size(); i++) {
printf("sa %d string %s height %d\n", sa[i], s.substr(sa[i], s.size()).c_str(), h[i]);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// codeforeces 633C
// link: https://codeforces.com/problemset/problem/633/C
#include <bits/stdc++.h>
using namespace std;
struct Node {
static const int SIZE = 26;
int ch[SIZE];
int val, fail, dep;
int endpoint;
Node() {
fail = 0, endpoint = -1;
memset(ch, 0, sizeof(ch));
}
};
struct ACAuto {
static const int N = 1e6+10;
Node t[N];
int counter = 1;
// A - Z, a - z
static int transform(char ch) {
if (ch >= 'A' && ch <= 'Z') return ch - 'A';
return ch - 'a';
}
void Insert(const char* s, int index) {
int root = 0;
for (int i = 0; s[i]; i++) {
int v = transform(s[i]);
if (!t[root].ch[v]) t[root].ch[v] = counter++;
root = t[root].ch[v];
t[root].val = v;
t[root].dep = i + 1;
}
t[root].endpoint = index;
}
void BFS() {
typedef pair<int, int> pii;
queue<pii> que;
que.push(pii(0, 0));
while (!que.empty()) {
pii p = que.front(); que.pop();
int u = p.first, pre = p.second;
for (int i = 0; i < Node::SIZE; i++) {
if (t[u].ch[i]) que.push(pii(t[u].ch[i], u));
}
if (u == 0) continue;
if (t[u].dep == 1) {
t[u].fail = 0;
continue;
}
int fail = t[pre].fail;
int val = t[u].val;
while (fail && t[fail].ch[val] == 0) fail = t[fail].fail;
t[u].fail = t[fail].ch[val];
}
}
void Init(const vector<const char*>& stringlist) {
for (int i = 0; i < stringlist.size(); i++) Insert(stringlist[i], i);
BFS();
}
int* Solve(const char* s) {
int root = 0, n = strlen(s), pos = 0;
int* dp = new int[n + 1];
memset(dp, -1, sizeof(int)*(n+1));
dp[0] = 0;
for (int i = 0; i < n; i++) {
int v = transform(s[i]);
while (pos && t[pos].ch[v] == 0) pos = t[pos].fail;
pos = t[pos].ch[v];
// printf("pos[%d]=%d\n", i+1, pos);
{
int fail = pos;
while (fail) {
if (t[fail].endpoint >= 0 && dp[i+1-t[fail].dep] >= 0) {
dp[i+1] = t[fail].endpoint;
break;
}
fail = t[fail].fail;
}
}
// printf("dp[%d]=%d\n\n", i+1, dp[i+1]);
}
assert(dp[n] >= 0);
return dp;
}
} acauto;
char buffer[1000000 + 100000 + 10];
char text[10010];
int pos[100010];
int len[100010];
void DFS(int index, const int* dp) {
if (index == 0) return ;
// printf("index: %d, dp: %d, pos: %d, len: %d\n", index, dp[index], pos[dp[index]], len[dp[index]]);
DFS(index - len[dp[index]], dp);
printf("%s ", buffer + pos[dp[index]]);
}
void solve() {
int n;
scanf("%d%s", &n, text);
vector<const char*> stringlist;
int m;
scanf("%d", &m);
stringlist.reserve(m);
for (int i = 0; i < m; i++) {
scanf("%s", buffer+pos[i]);
stringlist.push_back(buffer+pos[i]);
len[i] = strlen(buffer+pos[i]);
pos[i+1] = pos[i] + len[i] + 1;
reverse(buffer+pos[i], buffer+pos[i]+len[i]);
}
acauto.Init(stringlist);
// cout << "init succ" << endl;
const int* dp = acauto.Solve(text);
// cout << "solve succ" << endl;
for (int i = 0; i < m; i++)
reverse(buffer+pos[i], buffer+pos[i]+len[i]);
DFS(n, dp);
printf("\n");
}
int main() {
solve();
return 0;
}
// https://www.luogu.com.cn/problem/P3370
#include <bits/stdc++.h>
using namespace std;
template <int P, int MOD>
struct StringHash {
public:
StringHash() {}
StringHash(const char* s, int n) { Init(s, n); }
void Init(const char* s, int n) {
assert(1LL * P * INV % MOD == 1);
inv = hash = vector<int>(n);
int pw = 1;
for (int i = 0; i < n; i++) {
hash[i] = ((i ? hash[i-1] : 0) + 1LL * pw * (int)s[i]) % MOD;
inv[i] = i ? (1LL * inv[i-1] * INV % MOD) : 1;
pw = 1LL * pw * P % MOD;
}
}
int GetHash(int l, int r) const {
assert(r >= l - 1 && l >= 0 && r < (int)hash.size());
if (l > r) return 0;
if (l == 0) return hash[r];
return 1LL * (hash[r] - hash[l-1] + MOD) * inv[l] % MOD;
}
private:
constexpr static int PowMod(int a, int n) {
int ans = 1;
while (n) {
if (n & 1) ans = 1LL * ans * a % MOD;
a = 1LL * a * a % MOD;
n >>= 1;
}
return ans;
}
constexpr static int INV = PowMod(P, MOD - 2);
vector<int> hash, inv;
};
typedef StringHash<1009, 1000000007> Hasher;
// typedef StringHash<2003, 1000000009> Hasher2;
const int N = 1e5 + 10;
char buf[N];
int main() {
int n;
scanf("%d", &n);
set<int> st;
for (int i = 0; i < n; i++) {
scanf("%s", buf);
Hasher h(buf, strlen(buf));
st.insert(h.GetHash(0, strlen(buf)-1));
}
printf("%d\n", (int)st.size());
return 0;
}
// http://acm.hdu.edu.cn/showproblem.php?pid=3374
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6+10;
char s[N];
typedef std::function<bool(char, char)> LessFunc;
void solve(LessFunc leq) {
int n = strlen(s);
int i = 0, j = 1, k = 0;
while (k < n) {
// printf("i %d, j %d, k %d\n", i, j, k);
if (leq(s[(j+k)%n], s[(i+k)%n])) {
if (i+k+1 >= n) break;
(i += k+1) %= n;
k = 0;
} else if (leq(s[(i+k)%n], s[(j+k)%n])) {
if (j+k+1 >= n) break;
(j += k+1) %= n;
k = 0;
} else {
k++;
}
if (i == j) {
(j += 1) %= n;
if (j == 0) break;
}
}
printf("%d %d", i+1, n / (k == n ? abs(i-j) : n));
}
bool solve() {
if (scanf("%s", s) == 1) {
solve([](char a, char b) { return a < b; });
printf(" ");
solve([](char a, char b) { return a > b; });
printf("\n");
return true;
}
return false;
}
int main() {
while (solve());
return 0;
}
// author: yang12138
// https://atcoder.jp/contests/abc274/tasks/abc274_g
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static const int INF = 1e9;
struct NetFlow {
struct Edge {
int to, cap, rev;
Edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
};
vector<vector<Edge>> G;
vector<int> iter, level;
NetFlow(int V) : G(V), iter(V), level(V) {}
void AddEdge(int u, int v, int cap) {
G[u].push_back(Edge(v, cap, (int)G[v].size()));
G[v].push_back(Edge(u, 0, (int)G[u].size()-1));
}
void BFS(int s) {
fill(level.begin(), level.end(), -1);
level[s]=0;
queue<int> que;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for(int i = 0; i < G[v].size(); i++) {
Edge& e=G[v][i];
if(level[e.to] < 0 && e.cap > 0)
level[e.to] = level[v] + 1, que.push(e.to);
}
}
}
int DFS(int s, int t, int f) {
if (s == t) return f;
for (int& i = iter[s]; i < (int)G[s].size(); i++) {
Edge& e = G[s][i];
if (level[s] < level[e.to] && e.cap > 0) {
int d = DFS(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d, G[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int MaxFlow(int s, int t) {
int flow = 0;
while (BFS(s), level[t] >= 0) {
fill(iter.begin(), iter.end(), 0);
int f = 0;
while(f = DFS(s,t,INF)) flow += f;
}
return flow;
}
};
const int N = 305;
char str[N][N];
int up[N][N], lef[N][N];
void solve() {
int n, m;
scanf("%d%d", &n, &m);
auto GetNum = [&](int i, int j) { return (i - 1) * m + j; };
int s = 0, t = 2 * n * m + 1;
NetFlow nf(t + 1);
for (int i = 1; i <= n; i++) {
scanf("%s", str[i] + 1);
for (int j = 1; j <= m; j++) {
if (str[i][j] == '.') {
up[i][j] = (i - 1 >= 1 && str[i-1][j] == '.') ? up[i-1][j] : i;
lef[i][j] = (j - 1 >= 1 && str[i][j-1] == '.') ? lef[i][j-1] : j;
nf.AddEdge(GetNum(up[i][j], j), GetNum(i, lef[i][j]) + n * m, INF);
// printf("%d %d up %d lef %d\n", i, j, up[i][j], lef[i][j]);
}
nf.AddEdge(s, GetNum(i, j), 1);
nf.AddEdge(GetNum(i, j) + n * m, t, 1);
}
}
printf("%d\n", nf.MaxFlow(s, t));
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// http://codeforces.com/contest/1510/problem/B
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct Edge {
int to, cap, cost, rev;
Edge(int to, int cap, int cost, int rev) : to(to), cap(cap), cost(cost), rev(rev) {}
};
struct CostFlow {
static const int V = (1 << 11) + 10;
static const int INF = 1e9;
CostFlow(): n_(0) {}
void Reset() {
for (int i = 0; i < n_; i++) G[i].clear();
n_ = 0;
}
void AddEdge(int from, int to, int cap, int cost) {
G[from].push_back(Edge(to, cap, cost, G[to].size()));
G[to].push_back(Edge(from, 0, -cost, G[from].size() - 1));
}
void SetMax(int n) { n_ = n + 1; }
vector<Edge> G[V];
int h[V], dist[V];
int preV[V], preE[V];
int n_;
// 初始边权有正有负时不能用
int MinCostFlow(const int s, const int t, int max_flow, int* real_flow = nullptr) {
priority_queue<pii, vector<pii>, greater<pii> > que;
int res = 0;
memset(h, 0, sizeof(h[0])*n_);
while (max_flow) {
// printf("max_flow %d\n", max_flow);
for (int i = 0; i < n_; i++) dist[i] = INF;
dist[s] = 0;
que.push(pii(0, s));
while (!que.empty()) {
pii p = que.top();
que.pop();
int v = p.second;
if (dist[v] < p.first) continue;
for (int i = 0; i < G[v].size(); i++) {
const Edge& e = G[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
preV[e.to] = v, preE[e.to] = i;
que.push(pii(dist[e.to], e.to));
}
}
}
if (dist[t] == INF) return res;
for (int i = 0; i < n_; i++) h[i] += dist[i];
int cur_flow = max_flow;
for (int i = t; i != s; i = preV[i]) {
cur_flow = min(cur_flow, G[preV[i]][preE[i]].cap);
}
// printf("cur_flow %d dist[t]\n", cur_flow, dist[t]);
if (real_flow) *real_flow += cur_flow;
max_flow -= cur_flow;
res += cur_flow * h[t];
for (int i = t; i != s; i = preV[i]) {
Edge& e = G[preV[i]][preE[i]];
e.cap -= cur_flow, G[i][e.rev].cap += cur_flow;
}
}
return res;
}
int MinCostMaxFlow(const int s, const int t, int* real_flow = nullptr) {
return MinCostFlow(s, t, INF, real_flow);
}
const vector<Edge>* GetG() { return G; }
} min_cost_flow;
void solve() {
int d, n;
scanf("%d%d", &d, &n);
char buffer[20];
vector<int> st(n);
for (int i = 0; i < n; i++) {
scanf("%s", buffer);
for (int j = 0; j < d; j++) {
if (buffer[j] == '1') st[i] |= (1 << j);
}
}
sort(st.begin(), st.end());
vector<int> bits(1 << d);
vector<int> lastb(1 << d);
for (int i = 1; i < (1 << d); i++) {
bits[i] = bits[i/2] + (i&1);
if (i&1) lastb[i] = 0;
else lastb[i] = lastb[i/2]+1;
}
int s = 0, t = 2*n+1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if ((st[i] | st[j]) == st[i]) {
min_cost_flow.AddEdge(j+1, i+1+n, 1, -bits[st[j]]);
}
}
min_cost_flow.AddEdge(s, i+1, 1, 0);
min_cost_flow.AddEdge(i+1+n, t, 1, -1);
}
vector<int> in(1 << d, 0);
vector<int> vis(1 << d, 0);
vector<int> nex(1 << d);
int bs = 0;
for (auto i: st) in[i] = 1, bs += bits[i];
min_cost_flow.SetMax(t);
int flow = 0;
int cost = min_cost_flow.MinCostMaxFlow(s, t, &flow);
cost += n-1 + bs;
for (int i = 1; i <= n; i++) {
for (const Edge& e : min_cost_flow.GetG()[i]) {
if (e.to >= n+1 && e.to <= 2*n && e.cap == 0) {
nex[st[i-1]] = st[e.to-n-1];
break;
}
}
}
vector<char> ans;
int reset = 0, rcnt = 0;
for (int i = 1; i < (1 << d); i++) {
if (!in[i]) continue;
if (vis[i]) continue;
if (reset) ans.push_back('R'), rcnt++;
int pre = 0, cur = i;
while (cur) {
vis[cur] = 1;
int tmp = (pre ^ cur);
while (tmp) {
ans.push_back('0' + lastb[tmp]);
tmp ^= (1 << lastb[tmp]);
}
pre = cur, cur = nex[cur];
}
reset = 1;
}
/*
printf("reset cnt: %d, flow: %d\n", rcnt, flow);
printf("cost: %d, ans size: %d\n", cost, int(ans.size()));
*/
printf("%d\n", ans.size());
for (auto i: ans) printf("%c ", i);
printf("\n");
assert(rcnt == n-1-flow);
assert(cost == ans.size());
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
}
// https://acm.hdu.edu.cn/showproblem.php?pid=6081
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3005;
const int INF = 1e9;
struct Edge {
int u, v, w;
void scan() { scanf("%d%d%d", &u, &v, &w); }
};
struct DisjointSet {
int fa[N], n;
void Init(int n) {
this->n = n;
for (int i = 1; i <= n; i++) fa[i] = -1;
}
int FindFa(int u) {
return (fa[u] < 0) ? u : (fa[u] = FindFa(fa[u]));
}
bool Merge(int u, int v) {
u = FindFa(u), v = FindFa(v);
if (u == v) return true;
if (fa[u] + fa[v] == -n) return false;
fa[u] += fa[v];
fa[v] = u;
return true;
}
} ds;
bool solve() {
int n, m;
if (scanf("%d%d", &n, &m) != 2) return false;
vector<Edge> edges(m);
for (auto& edge : edges) edge.scan();
int ans = INF;
int unchange = 0;
const int LIMIT = 2000;
do {
random_shuffle(edges.begin(), edges.end());
ds.Init(n);
bool flag = false;
for (const auto& edge : edges) {
if (!ds.Merge(edge.u, edge.v)) {
flag = true;
break;
}
}
if (!flag) {
ans = 0;
break;
}
int tans = 0;
for (const auto& edge : edges) {
if (ds.FindFa(edge.u) != ds.FindFa(edge.v)) {
tans += edge.w;
}
}
if (ans <= tans) unchange++;
else ans = tans, unchange = 0;
// printf("tans %d, ans %d\n", tans, ans);
} while (unchange <= LIMIT);
printf("%d\n", ans);
return true;
}
int main() {
while (solve());
return 0;
}
// https://acm.hdu.edu.cn/showproblem.php?pid=2255
// https://acm.hdu.edu.cn/showproblem.php?pid=6346
// KM algorithm
// MaxWeightMatch of bipartite graph
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
const int INF = 2e9;
int A[N], B[N], slack[N];
int w[N][N];
// all rig
int match[N], repl[N];
bool vis[N];
int nx, ny;
ll KM() {
assert(nx >= 1 && ny >= 1 && nx <= ny);
std::fill(match + 1, match + ny + 1, -1);
for(int x = 1; x <= nx; x++) {
int currig = 0;
match[currig] = x;
std::fill(vis, vis + ny + 1, false);
std::fill(slack + 1, slack + ny + 1, INF);
while (match[currig] != -1) {
vis[currig] = true;
int curlef = match[currig], nexrig = -1;
ll d = INF;
for (int y = 1; y <= ny; y++) {
if (!vis[y]) {
ll t = A[curlef] + B[y] - w[curlef][y];
if (t < slack[y]) slack[y] = t, repl[y] = currig;
if (slack[y] < d) d = slack[y], nexrig = y;
}
}
for (int y = 0; y <= ny; y++) {
if (vis[y]) A[match[y]] -= d, B[y] += d;
else slack[y] -= d;
}
currig = nexrig;
}
while (currig) {
int nexrig = repl[currig];
match[currig] = match[nexrig];
currig = nexrig;
}
}
ll ans = 0;
for (int i = 1; i <= ny; i++) {
if (match[i] > 0) ans += B[i] + A[match[i]];
}
return ans;
}
void solve(int cas) {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &w[i][j]);
w[i][j] *= -1;
}
}
nx = ny = n;
printf("Case #%d: %lld\n", cas, -KM());
}
int main() {
int T, t = 0;
scanf("%d", &T);
while (T--) solve(++t);
return 0;
}
// https://www.luogu.com.cn/problem/P1501
// https://www.luogu.com.cn/problem/P2147
// https://www.luogu.com.cn/problem/P3690
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5+10;
const int MOD = 51061;
int ch[N][2], f[N];
struct Value {
int mul = 0, add = 0, val = 0, sum = 0, sz = 0, tag = 0;
Value() {}
Value(int mul, int add, int tag = 0): mul(mul), add(add), tag(tag) {}
void PushDown(Value& rhs) const {
if (mul != 1) {
rhs.mul = 1LL * rhs.mul * mul % MOD;
rhs.add = 1LL * rhs.add * mul % MOD;
rhs.val = 1LL * rhs.val * mul % MOD;
rhs.sum = 1LL * rhs.sum * mul % MOD;
}
if (add) {
(rhs.add += add) %= MOD;
(rhs.val += add) %= MOD;
(rhs.sum += 1LL * rhs.sz * add % MOD) %= MOD;
}
if (tag) rhs.tag ^= 1;
}
void PushUp(const Value& lhs, const Value& rhs) {
sz = lhs.sz + rhs.sz + 1;
sum = (lhs.sum + rhs.sum + val) % MOD;
}
void Reset() {
mul = 1, add = 0, tag = 0;
}
} val[N];
int Get(int x) { return ch[f[x]][1] == x; }
bool IsSplayRoot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }
void PushDown(int x) {
if (val[x].tag) swap(ch[x][0], ch[x][1]);
if (ch[x][0]) val[x].PushDown(val[ch[x][0]]);
if (ch[x][1]) val[x].PushDown(val[ch[x][1]]);
val[x].Reset();
}
void PushUp(int x) { val[x].PushUp(val[ch[x][0]], val[ch[x][1]]); }
void Update(int x) { if (!IsSplayRoot(x)) Update(f[x]); PushDown(x); }
void Rotate(int x) {
assert(f[x]);
int y = f[x], k = Get(x);
// link y and ch[x][!k]
if (ch[x][!k]) f[ch[x][!k]] = y;
ch[y][k] = ch[x][!k];
// link f[y] and x
if (!IsSplayRoot(y)) ch[f[y]][Get(y)] = x;
f[x] = f[y];
// link x and y
ch[x][!k] = y, f[y] = x;
PushUp(y), PushUp(x);
}
void Splay(int x) {
Update(x);
for (int fa = f[x]; !IsSplayRoot(x); fa = f[x]) {
if (!IsSplayRoot(fa) && !IsSplayRoot(f[fa]))
Rotate(Get(fa) == Get(x) ? fa : x);
Rotate(x);
}
}
int Access(int x) {
int p = 0;
while (x) {
Splay(x), ch[x][1] = p, PushUp(x);
p = x, x = f[x];
}
return p;
}
void MakeRoot(int x) { val[Access(x)].tag ^= 1; }
void Link(int x, int y) { MakeRoot(x), Splay(x), f[x] = y; }
void Split(int x, int y) { MakeRoot(x), Access(y), Splay(x); }
void Cut(int x, int y) { Split(x, y), Splay(y), ch[y][0] = f[x] = 0; }
int FindRoot(int x) {
Access(x), Splay(x);
while (ch[x][0]) PushDown(x), x = ch[x][0];
Splay(x);
return x;
}
void solve() {
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
val[i].mul = val[i].val = val[i].sz = val[i].sum = 1;
}
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
Link(u, v);
}
char s[10];
while (q--) {
int u1, v1, u2, v2, c;
scanf("%s%d%d", s, &u1, &v1);
if (s[0] == '+') {
scanf("%d", &c);
Split(u1, v1);
Value(1, c).PushDown(val[u1]);
} else if (s[0] == '-') {
scanf("%d%d", &u2, &v2);
Cut(u1, v1);
Link(u2, v2);
} else if (s[0] == '*') {
scanf("%d", &c);
Split(u1, v1);
Value(c, 0).PushDown(val[u1]);
} else {
Split(u1, v1);
printf("%d\n", val[u1].sum);
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// https://loj.ac/p/2230
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5+10;
int ch[N][2], f[N];
struct Value {
int tag = 0;
int splay_size = 0, subtree_size = 0, virtualson_size = 0;
Value() {}
void PushDown(Value& rhs) const {
if (tag) rhs.tag ^= 1;
}
void PushUp(const Value& lhs, const Value& rhs) {
splay_size = lhs.splay_size + rhs.splay_size + 1;
subtree_size = lhs.subtree_size + rhs.subtree_size + 1 + virtualson_size;
}
void Reset() { tag = 0; }
} val[N];
int Get(int x) { return ch[f[x]][1] == x; }
bool IsSplayRoot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }
void PushDown(int x) {
if (val[x].tag) swap(ch[x][0], ch[x][1]);
if (ch[x][0]) val[x].PushDown(val[ch[x][0]]);
if (ch[x][1]) val[x].PushDown(val[ch[x][1]]);
val[x].Reset();
}
void PushUp(int x) { val[x].PushUp(val[ch[x][0]], val[ch[x][1]]); }
void Update(int x) { if (!IsSplayRoot(x)) Update(f[x]); PushDown(x); }
void Rotate(int x) {
assert(f[x]);
int y = f[x], k = Get(x);
// link y and ch[x][!k]
if (ch[x][!k]) f[ch[x][!k]] = y;
ch[y][k] = ch[x][!k];
// link f[y] and x
if (!IsSplayRoot(y)) ch[f[y]][Get(y)] = x;
f[x] = f[y];
// link x and y
ch[x][!k] = y, f[y] = x;
PushUp(y), PushUp(x);
}
void Splay(int x) {
Update(x);
for (int fa = f[x]; !IsSplayRoot(x); fa = f[x]) {
if (!IsSplayRoot(fa) && !IsSplayRoot(f[fa]))
Rotate(Get(fa) == Get(x) ? fa : x);
Rotate(x);
}
}
int Access(int x) {
int p = 0;
while (x) {
Splay(x);
val[x].virtualson_size += val[ch[x][1]].subtree_size - val[p].subtree_size;
ch[x][1] = p, PushUp(x);
p = x, x = f[x];
}
return p;
}
void MakeRoot(int x) { val[Access(x)].tag ^= 1; }
void Link(int x, int y) {
MakeRoot(x), Splay(x);
MakeRoot(y), Splay(y);
f[x] = y, val[y].virtualson_size += val[x].subtree_size;
}
void Split(int x, int y) { MakeRoot(x), Access(y), Splay(x); }
void Cut(int x, int y) { Split(x, y), Splay(y), ch[y][0] = f[x] = 0; }
int FindRoot(int x) {
Access(x), Splay(x);
while (ch[x][0]) PushDown(x), x = ch[x][0];
Splay(x);
return x;
}
int GetTreeSize(int x) {
MakeRoot(x), Splay(x);
return val[x].subtree_size;
}
void solve() {
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) val[i].subtree_size = 1;
while (q--) {
char op[4];
int x, y;
scanf("%s%d%d", op, &x, &y);
if (op[0] == 'A') {
Link(x, y);
} else {
Cut(x, y);
printf("%lld\n", 1LL * GetTreeSize(x) * GetTreeSize(y));
Link(x, y);
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct PairingHeap {
public:
static const int N = 3e5+10;
PairingHeap() { Reset(N - 1); }
void Reset(int n) {
root = 0;
std::memset(val, sizeof(val[0]) * (n + 1), 0);
std::fill(son, son + n + 1, 0);
std::fill(pre, pre + n + 1, 0);
std::fill(bro, bro + n + 1, 0);
}
const T& GetVal(int u) const { return val[u]; }
bool InHeap(int u) const { return u == root || pre[u] != 0; }
bool Empty() const { return root ? false : true; }
T Top() const {
assert(!Empty());
return val[root];
}
void Push(int u, T x) {
assert(son[u] == 0 && pre[u] == 0 && bro[u] == 0);
val[u] = x;
root = Merge(root, u);
}
void Pop() {
assert(!Empty());
int tmp = Merges(son[root]);
ResetNode(root);
root = tmp;
}
void Update(int u, T x) {
assert(x < val[u]);
val[u] = x;
if (u == root) return ;
assert(pre[u]);
if (son[pre[u]] == u) son[pre[u]] = bro[u];
else bro[pre[u]] = bro[u];
if (bro[u]) pre[bro[u]] = pre[u];
root = Merge(root, u);
}
private:
void ResetNode(int u) { son[u] = pre[u] = bro[u] = 0; }
void MakeRoot(int u) { pre[u] = bro[u] = 0; }
int Merge(int u, int v) {
MakeRoot(u), MakeRoot(v);
if (u == 0 || v == 0) return u ^ v;
if (val[u] > val[v]) swap(u, v);
bro[v] = son[u];
if (son[u]) pre[son[u]] = v;
son[u] = v;
pre[v] = u;
return u;
}
int Merges(int u) {
if (u == 0) return 0;
int v = bro[u], w = bro[v];
return Merge(Merge(u, v), Merges(w));
}
T val[N];
int son[N], pre[N], bro[N], root;
};
int main() {
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SkipListNode;
struct SkipListLevel {
SkipListNode* forward = nullptr;
int span;
};
struct SkipListNode {
int score;
int obj;
SkipListLevel *level;
};
const int MAX_LEVEL = 20;
int RandomLevel() {
int level = 1;
while (level < MAX_LEVEL && rand() % 2 == 0) level++;
return level;
}
SkipListNode* CreateSkipListNode(int level, int score, int obj) {
SkipListNode* node = new SkipListNode;
node->score = score;
node->obj = obj;
node->level = new SkipListLevel[level];
return node;
}
struct SkipList {
SkipListNode* header_;
int level_;
int len_;
SkipList() {
header_ = CreateSkipListNode(MAX_LEVEL, 0, 0);
level_ = len_ = 0;
}
void Insert(int score, int obj) {
SkipListNode *update[MAX_LEVEL];
int rank[MAX_LEVEL];
SkipListNode* x = header_;
for (int i = level_ - 1; i >= 0; i--) {
rank[i] = (i == level_ - 1) ? 0 : rank[i + 1];
while (x->level[i].forward && (x->level[i].forward->score < score ||
x->level[i].forward->score == score &&
x->level[i].forward->obj < obj)) {
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
int newlevel = RandomLevel();
if (newlevel > level_) {
for (int i = level_; i < newlevel; i++) {
update[i] = header_;
update[i]->level[i].span = len_;
rank[i] = 0;
}
}
x = CreateSkipListNode(newlevel, score, obj);
for (int i = 0; i < newlevel; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = rank[0] - rank[i] + 1;
}
for (int i = newlevel; i < level_; i++) update[i]->level[i].span++;
level_ = max(level_, newlevel);
len_++;
}
int Delete(int score, int obj) {
SkipListNode *update[MAX_LEVEL];
int rank[MAX_LEVEL];
SkipListNode* x = header_;
for (int i = level_ - 1; i >= 0; i--) {
while (x->level[i].forward && (x->level[i].forward->score < score ||
x->level[i].forward->score == score &&
x->level[i].forward->obj < obj)) {
// rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
if (!(x->level[0].forward && x->level[0].forward->score == score &&
x->level[0].forward->obj == obj)) return -1;
x = x->level[0].forward;
for (int i = 0; i < level_; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].forward = x->level[i].forward;
update[i]->level[i].span += x->level[i].span - 1;
} else {
update[i]->level[i].span--;
}
}
len_--;
return 0;
}
// rank from 1
int GetByRank(int rank, int& score, int& obj) const {
if (rank <= 0 || rank > len_) return -1;
SkipListNode* x = header_;
for (int i = level_ - 1; i >= 0 && rank; i--) {
while (x->level[i].forward && rank >= x->level[i].span) {
rank -= x->level[i].span;
x = x->level[i].forward;
}
}
score = x->score;
obj = x->obj;
return 0;
}
int GetByScore(int score, int& obj) const {
SkipListNode* x = header_;
for (int i = level_ - 1; i >= 0; i--) {
while (x->level[i].forward && x->level[i].forward->score < score) {
x = x->level[i].forward;
}
}
if (x->level[0].forward && x->level[0].forward->score == score) {
obj = x->level[0].forward->obj;
return 0;
}
return -1;
}
void Dump() const {
SkipListNode* x = header_->level[0].forward;
printf("size: %d\n", len_);
while (x) {
printf("(%d, %d)\n", x->score, x->obj);
x = x->level[0].forward;
}
}
};
int main() {
SkipList sl;
while (1) {
int type;
int score, obj;
scanf("%d", &type);
if (type == 1) {
scanf("%d%d", &score, &obj);
sl.Insert(score, obj);
sl.Dump();
} else if (type == 2) {
int rank;
scanf("%d", &rank);
int ret = sl.GetByRank(rank, score, obj);
printf("ret=%d, rank %d: (%d, %d)\n", ret, rank, score, obj);
} else if (type == 3) {
scanf("%d", &score);
int ret = sl.GetByScore(score, obj);
printf("ret=%d, (%d, %d)\n", ret, score, obj);
} else if (type == 4) {
scanf("%d%d", &score, &obj);
int ret = sl.Delete(score, obj);
printf("ret=%d\n", ret);
sl.Dump();
}
}
return 0;
}
// https://loj.ac/p/104
// https://loj.ac/p/105
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6+10;
const int INF = 1e9;
struct SplayNode {
int weight = 0;
int cnt = 0, sum = 0;
int rev = 0;
SplayNode* ch[2] = {};
SplayNode* fa = nullptr;
int Get() const { return this == fa->ch[1]; }
void Maintain();
void Rotate();
SplayNode* Splay();
SplayNode* Insert(int x);
// x must exist
SplayNode* Delete(int x);
// x must exist
int Rank(int x) const;
// 1 <= k <= root->sum
SplayNode* Kth(int k);
int Pre(int x) const;
int Suc(int x) const;
SplayNode* GetMax() {
return this->ch[1] ? this->ch[1]->GetMax() : this;
}
void PushDown();
void Traverse(vector<int>&);
} nodes[N];
SplayNode* NewNode() {
static int counter = 0;
return nodes + (counter++);
}
void SplayNode::Maintain() {
/*
assert(!ch[0] || (weight > ch[0]->weight && ch[0]->cnt));
assert(!ch[1] || (weight < ch[1]->weight && ch[1]->cnt));
*/
sum = (ch[0] ? ch[0]->sum : 0) + (ch[1] ? ch[1]->sum : 0) + cnt;
}
void SplayNode::Rotate() {
assert(this->rev == 0);
// cerr << "Rorate " << this << endl;
SplayNode* f = this->fa;
assert(f);
int flag = this->Get();
if (f->fa) {
f->fa->ch[f->Get()] = this;
}
this->fa = f->fa;
f->ch[flag] = this->ch[flag ^ 1];
if (this->ch[flag ^ 1]) this->ch[flag ^ 1]->fa = f;
this->ch[flag ^ 1] = f;
f->fa = this;
f->Maintain();
this->Maintain();
}
SplayNode* SplayNode::Splay() {
// cerr << "Splay " << this << endl;
while (this->fa) {
this->Rotate();
}
return this;
}
SplayNode* SplayNode::Insert(int x) {
// cerr << "Insert " << this << ' ' << x << endl;
this->sum++;
if (x == this->weight) {
this->cnt++;
return this;
}
int flag = (x > this->weight);
if (this->ch[flag])
return this->ch[flag]->Insert(x);
SplayNode* resp = NewNode();
resp->weight = x;
resp->cnt = 1, resp->sum = 1;
this->ch[flag] = resp;
resp->fa = this;
return resp;
}
SplayNode* SplayNode::Delete(int x) {
// cerr << "Delete " << this << ' ' << x << endl;
this->sum--;
if (x == this->weight) {
assert(this->cnt >= 1);
this->cnt--;
return this;
}
assert(this->ch[x > this->weight]);
return this->ch[x > this->weight]->Delete(x);
}
int SplayNode::Rank(int x) const {
if (this->weight == x) return this->ch[0] ? this->ch[0]->sum : 0;
if (this->weight > x) return this->ch[0] ? this->ch[0]->Rank(x) : 0;
return (this->ch[0] ? this->ch[0]->sum : 0) + this->cnt + (this->ch[1] ? this->ch[1]->Rank(x) : 0);
}
SplayNode* SplayNode::Kth(int k) {
this->PushDown();
if (this->ch[0] && this->ch[0]->sum >= k)
return this->ch[0]->Kth(k);
k -= (this->ch[0] ? this->ch[0]->sum : 0);
if (this->cnt >= k) return this;
return this->ch[1]->Kth(k - this->cnt);
}
int SplayNode::Pre(int x) const {
if (x <= this->weight) return this->ch[0] ? this->ch[0]->Pre(x) : -INF;
return max(this->weight, this->ch[1] ? this->ch[1]->Pre(x) : -INF);
}
int SplayNode::Suc(int x) const {
if (x >= this->weight) return this->ch[1] ? this->ch[1]->Suc(x) : INF;
return min(this->weight, this->ch[0] ? this->ch[0]->Suc(x) : INF);
}
void SplayNode::PushDown() {
if (this->rev) {
if (this->ch[0]) this->ch[0]->rev ^= 1;
if (this->ch[1]) this->ch[1]->rev ^= 1;
swap(this->ch[0], this->ch[1]);
this->rev = 0;
}
}
void SplayNode::Traverse(vector<int>& res) {
this->PushDown();
if (this->ch[0]) this->ch[0]->Traverse(res);
res.push_back(this->weight);
if (this->ch[1]) this->ch[1]->Traverse(res);
}
struct SplayTree {
SplayNode* root = nullptr;
void Insert(int x) {
if (root == nullptr) {
root = NewNode();
root->weight = x;
root->cnt = root->sum = 1;
} else {
root = root->Insert(x)->Splay();
}
}
void Delete(int x) {
root = root->Delete(x)->Splay();
if (root->cnt == 0) {
if (root->ch[0] == nullptr) {
root = root->ch[1];
root->fa = nullptr;
} else if (root->ch[1] == nullptr) {
root = root->ch[0];
root->fa = nullptr;
} else {
root->ch[0]->fa = nullptr;
SplayNode* s = root->ch[0]->GetMax();
s->Splay();
assert(s->ch[1] == nullptr);
s->ch[1] = root->ch[1];
root->ch[1]->fa = s;
s->Maintain();
root = s;
}
}
}
int Rank(int x) { return root->Rank(x); }
SplayNode* Kth(int x) { return root->Kth(x); }
int Pre(int x) { return root->Pre(x); }
int Suc(int x) { return root->Suc(x); }
void Traverse(vector<int>& res) { root->Traverse(res); }
};
void solve() {
int n, m;
scanf("%d%d", &n, &m);
SplayTree tr;
for (int i = 0; i <= n+1; i++) tr.Insert(i);
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
tr.root = tr.Kth(l-1 + 1)->Splay();
tr.root = tr.Kth(r+1 + 1)->Splay();
assert(tr.root->ch[0]);
assert(tr.root->ch[0]->ch[1]);
tr.root->ch[0]->ch[1]->rev ^= 1;
}
vector<int> ans;
tr.Traverse(ans);
assert(ans.size() == n+2);
for (int i = 1; i <= n; i++) {
if (i > 1) printf(" ");
printf("%d", ans[i]);
}
printf("\n");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct TreapNode {
static const int SIZE = 1e5 + 10;
static int counter;
TreapNode *son[2], *fa;
int val, rank, size, id;
void Reset() {
son[0] = son[1] = fa = nullptr;
rank = rand();
}
TreapNode() { Reset(); }
void PushUp() {
size = 1;
if (son[0]) size += son[0]->size;
if (son[1]) size += son[1]->size;
}
void print() const {
printf("id: %d, val: %d\n", id, val);
}
} nodes[TreapNode::SIZE];
int TreapNode::counter = 0;
TreapNode* CreateTreapNode(int val, int id) {
TreapNode* node = &nodes[TreapNode::counter++];
node->val = val;
node->id = id;
node->size = 1;
return node;
}
struct Treap {
TreapNode* head;
void Reset() {
for (int i = 0; i < TreapNode::counter; i++) nodes[i].Reset();
TreapNode::counter = 0;
head = CreateTreapNode(INT_MIN, 0);
head->rank = -1;
}
Treap() { Reset(); }
static int SonType(TreapNode* x) {
return x->fa->son[1] == x;
}
static void GenChildren(TreapNode* fa, TreapNode* son, int type) {
fa->son[type] = son;
if (son) son->fa = fa;
}
// if exist already, ingore
void Insert(int val, int id) {
TreapNode* x = CreateTreapNode(val, id);
TreapNode* cur = head;
while (1) {
// if (cur->val == val) return;
cur->size++;
int flag = cur->val < val;
if (cur->son[flag] == nullptr) { cur->son[flag] = x, x->fa = cur; break; }
else cur = cur->son[flag];
}
assert(x->fa);
while (x->rank < x->fa->rank) {
int flag = SonType(x);
TreapNode* fa = x->fa;
assert(fa->fa);
GenChildren(fa->fa, x, SonType(fa));
GenChildren(fa, x->son[flag^1], flag);
GenChildren(x, fa, flag^1);
fa->PushUp();
x->PushUp();
}
}
// todo
void Delete(int val) {
}
const TreapNode* SeekUpperBound(int val) {
TreapNode* cur = head;
TreapNode* ans = nullptr;
while (cur) {
if (cur->val > val) ans = cur, cur = cur->son[0];
else cur = cur->son[1];
}
// assert(ans);
return ans;
}
const TreapNode* SeekLowerBound(int val) {
TreapNode* cur = head;
TreapNode* ans = nullptr;
while (cur) {
if (cur->val < val) ans = cur, cur = cur->son[1];
else cur = cur->son[0];
}
// assert(ans);
return ans;
}
// from 1
const TreapNode* GetByRank(int rank) {
rank++;
TreapNode* cur = head;
if (rank > cur->size) return nullptr;
while (cur) {
if (cur->son[0]) {
if (cur->son[0]->size >= rank) { cur = cur->son[0]; continue; }
rank -= cur->son[0]->size;
}
if (rank == 1) return cur;
rank--;
cur = cur->son[1];
}
return nullptr;
}
} treap;
void SolveHDU4585() {
int n;
while (~scanf("%d", &n) && n) {
treap.Reset();
treap.Insert(1000000000, 1);
treap.Insert(-1000000000, 1);
int id, val;
while (n--) {
scanf("%d%d", &id, &val);
treap.Insert(val, id);
const TreapNode* lower = treap.SeekLowerBound(val);
const TreapNode* upper = treap.SeekUpperBound(val);
if (val - lower->val <= upper->val - val) {
printf("%d %d\n", id, lower->id);
} else {
printf("%d %d\n", id, upper->id);
}
}
}
}
void SolveUVA10107() {
int n, counter = 0;
while (~scanf("%d", &n)) {
counter++;
treap.Insert(n, 0);
if (counter & 1) {
printf("%d\n", treap.GetByRank(counter/2 + 1)->val);
} else {
printf("%lld\n", (0LL + treap.GetByRank(counter/2)->val + treap.GetByRank(counter/2+1)->val)/2);
}
}
}
int main() {
SolveUVA10107();
// SolveHDU4585();
return 0;
}
// https://atcoder.jp/contests/abc210/tasks/abc210_f
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct SCC {
static const int N = 30000 * 22 * 2 * 2 + 100;
vector<int> G[N];
vector<int> rG[N];
bool vis[N];
int id[N];
vector<int> cmp[N];
SCC() {
memset(vis, 0, sizeof(vis));
}
// a --> b
// !a || b
// a -> b and !b -> !a
void Infer(int u, int v) {
AddEdge(u, v);
AddEdge(v^1, u^1);
}
void AddEdge(int u, int v) {
G[u].push_back(v);
rG[v].push_back(u);
}
void dfs(int u, vector<int>& orders) {
vis[u] = 1;
for (const int v : G[u]) {
if (!vis[v]) dfs(v, orders);
}
orders.push_back(u);
}
void rdfs(int u, int k) {
vis[u] = 1;
id[u] = k, cmp[k].push_back(u);
for (const int v : rG[u]) {
if (!vis[v]) rdfs(v, k);
}
}
void run(int n) {
vector<int> orders;
for (int i = 0; i < n; i++) {
if (!vis[i]) dfs(i, orders);
}
reverse(orders.begin(), orders.end());
std::fill(vis, vis+n, false);
int k = 0;
for (const int u : orders) {
if (!vis[u]) {
rdfs(u, ++k);
}
}
}
} scc;
const int M = 2e6 + 10;
int mip[M];
vector<int> primes;
void init() {
mip[1] = 1;
for (int i = 2; i < M; i++) {
if (mip[i] == 0) mip[i] = i, primes.push_back(i);
for (const int p : primes) {
int u = p * i;
if (u >= M) break;
mip[u] = p;
if (i % p == 0) break;
}
}
}
vector<int> GetPrimeFactors(int n) {
vector<int> res;
while (n > 1) {
int p = mip[n];
res.push_back(p);
while (n % p == 0) n /= p;
}
return res;
}
vector<pii> X[M];
void solve() {
init();
int n;
scanf("%d", &n);
int cur = n;
for (int i = 0; i < n; i++) {
int a, b;
scanf("%d%d", &a, &b);
for (const int p : GetPrimeFactors(a)) {
X[p].push_back(pii(i << 1, cur++ << 1));
}
for (const int p : GetPrimeFactors(b)) {
X[p].push_back(pii(i << 1 | 1, cur++ << 1));
}
}
for (int i = 2; i < M; i++) {
const auto& xp = X[i];
int sz = xp.size();
if (sz <= 1) continue;
for (int i = 0; i < sz; i++) {
if (i+1 < sz) {
scc.Infer(xp[i].first, xp[i+1].second);
scc.Infer(xp[i].second, xp[i+1].second);
}
scc.Infer(xp[i].second, xp[i].first ^ 1);
}
}
scc.run(2*cur);
// topo order of x > topo order of !x <==> x is ture
for (int i = 0; i < cur; i++) {
if (scc.id[i << 1] == scc.id[i << 1 | 1]) {
printf("No\n");
return ;
}
}
printf("Yes\n");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// author: yang12138
// https://www.luogu.com.cn/problem/P3388
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5+10;
const int M = 1e5+10;
vector<pii> G[N];
int low[N], ord[N], cnt = 0;
bool vise[M];
void DFS(int u, int f, vector<int>& ans) {
ord[u] = low[u] = ++cnt;
bool flag = 0;
int son = 0;
for (auto [v, eid] : G[u]) {
if (vise[eid]) continue;
vise[eid] = 1;
if (!low[v]) {
DFS(v, u, ans);
low[u] = min(low[u], low[v]);
if (low[v] >= ord[u]) flag = 1;
son++;
} else {
low[u] = min(low[u], ord[v]);
}
}
if (f ? flag : (son > 1)) {
ans.push_back(u);
}
}
void solve() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(pii(v, i));
G[v].push_back(pii(u, i));
}
vector<int> ans;
for (int i = 1; i <= n; i++)
if (!low[i])
DFS(i, 0, ans);
sort(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for (int i : ans) printf("%d ", i);
printf("\n");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// author: yang12138
// https://www.luogu.com.cn/problem/P2860
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5+10;
const int M = 1e5+10;
vector<pii> G[N];
vector<int> G2[N];
vector<pii> edges;
int low[N], ord[N], cnt = 0;
bool vise[M];
int id[N], deg[N];
void DFS(int u, int f) {
ord[u] = low[u] = ++cnt;
for (auto [v, eid] : G[u]) {
if (vise[eid]) continue;
vise[eid] = 1;
if (!low[v])
DFS(v, u), low[u] = min(low[u], low[v]);
else
low[u] = min(low[u], ord[v]);
}
if (low[u] < ord[u]) {
G2[u].push_back(f);
G2[f].push_back(u);
}
}
void DFS2(int u, int k) {
id[u] = k;
for (auto v : G2[u])
if (!id[v]) DFS2(v, k);
}
void solve() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(pii(v, i));
G[v].push_back(pii(u, i));
edges.push_back(pii(u, v));
}
DFS(1, 0);
int k = 0;
for (int i = 1; i <= n; i++)
if (!id[i]) DFS2(i, ++k);
int ecnt = 0;
for (auto [u, v] : edges) {
if (id[u] != id[v])
deg[id[u]]++, deg[id[v]]++, ecnt++;
}
assert(ecnt == k - 1);
int ans = 0;
for (int i = 1; i <= k; i++) {
ans += (deg[i] == 1);
}
printf("%d\n", k == 1 ? 0 : (ans + 1) / 2);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// http://poj.org/problem?id=1741
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e4 + 10;
const int INF = 1e9;
vector<pii> G[N];
bool is_centroid[N];
int D;
int GetSubTreeSize(int u, int f) {
int ans = 1;
for (const auto pir : G[u]) {
int v = pir.first;
if (is_centroid[v] || v == f) continue;
ans += GetSubTreeSize(v, u);
}
return ans;
}
int SearchCentroid(int u, int f, const int size, pii& res) {
int maxsize = 0, sum = 0;
for (const auto pir : G[u]) {
int v = pir.first;
if (is_centroid[v] || v == f) continue;
int tmp = SearchCentroid(v, u, size, res);
maxsize = max(maxsize, tmp);
sum += tmp;
}
maxsize = max(maxsize, size - 1 - sum);
if (maxsize < res.first) res = pii(maxsize, u);
return sum + 1;
}
void GetPaths(int u, int f, int d, vector<int>& paths) {
paths.push_back(d);
for (const auto pir : G[u]) {
int v = pir.first;
if (is_centroid[v] || v == f) continue;
GetPaths(v, u, d + pir.second, paths);
}
}
int Calc(vector<int>& ds) {
sort(ds.begin(), ds.end());
int l = 0, r = ds.size() - 1;
int ans = 0;
while (l < r) {
while (r > l && ds[l] + ds[r] > D) r--;
if (r <= l) break;
ans += r - l;
l++;
}
return ans;
}
void DivideAndConquer(int u, int& ans) {
int size = GetSubTreeSize(u, 0);
pii res(INF, 0);
SearchCentroid(u, 0, size, res);
const int root = res.second;
assert(root);
is_centroid[root] = 1;
vector<int> paths = {0};
for (const auto pir : G[root]) {
int v = pir.first;
if (!is_centroid[v]) {
DivideAndConquer(v, ans);
vector<int> tmp;
GetPaths(v, 0, pir.second, tmp);
paths.insert(paths.end(), tmp.begin(), tmp.end());
ans -= Calc(tmp);
}
}
ans += Calc(paths);
is_centroid[root] = 0;
}
bool solve() {
int n;
scanf("%d%d", &n, &D);
if (n == 0 && D == 0) return false;
for (int i = 1; i <= n; i++) G[i].clear();
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(pii(v, w));
G[v].push_back(pii(u, w));
}
int ans = 0;
DivideAndConquer(1, ans);
printf("%d\n", ans);
return true;
}
int main() {
while (solve());
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef bitset<100010> BitSet;
const int N = 3005;
vector<int> G[N];
int sz[N], is_centroid[N], w[N];
int FindTreeSize(int u, int f) {
int ret = 1;
for (int v : G[u]) {
if (v == f || is_centroid[v]) continue;
ret += FindTreeSize(v, u);
}
return ret;
}
pii FindRoot(int u, int f, int ssz) {
sz[u] = 1;
pii ret(N, 0);
int ma = 0;
for (int v : G[u]) {
if (v == f || is_centroid[v]) continue;
ret = min(ret, FindRoot(v, u, ssz));
sz[u] += sz[v];
ma = max(ma, sz[v]);
}
ma = max(ma, ssz - sz[u]);
return min(ret, pii(ma, u));
}
void DP(int u, int f, BitSet& pre) {
BitSet cur = (pre << w[u]);
for (int v : G[u]) {
if (v == f || is_centroid[v]) continue;
DP(v, u, cur);
}
pre |= cur;
}
void DFS(int u, BitSet& ret) {
int root = FindRoot(u, 0, FindTreeSize(u, 0)).second;
assert(root);
BitSet bs;
bs[0] = 1;
DP(root, 0, bs);
ret |= bs;
is_centroid[root] = 1;
for (int v : G[root]) {
if (!is_centroid[v]) {
DFS(v, ret);
}
}
is_centroid[root] = 0;
}
void solve() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
G[i].clear();
sz[i] = is_centroid[i] = 0;
}
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
scanf("%d", w + i);
}
BitSet ret;
DFS(1, ret);
for (int i = 1; i <= m; i++) printf("%d", int(ret[i]));
printf("\n");
}
int main() {
int T;
scanf("%d", &T);
while (T--) solve();
return 0;
}
// https://www.luogu.com.cn/problem/P6192
// n points, m edges, k key points
// O(n3^k) + O(2^kmlogn)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 105;
const int K = 10;
const int INF = 1e9;
int key_point[K];
vector<pii> G[N];
priority_queue<pii, vector<pii>, greater<pii>> que;
void Dijkstra(int* dis) {
while (!que.empty()) {
pii t = que.top(); que.pop();
int u = t.second;
if (dis[u] < t.first) continue;
for (auto e : G[u]) {
int v = e.first, w = e.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
que.push(pii(dis[v], v));
}
}
}
}
int dis[1 << K][N];
void solve() {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(pii(v, w));
G[v].push_back(pii(u, w));
}
for (int s = 1; s < (1 << k); s++) fill(dis[s] + 1, dis[s] + n + 1, INF);
for (int i = 0; i < k; i++) {
scanf("%d", key_point + i);
dis[1 << i][key_point[i]] = 0;
}
for (int s = 1; s < (1 << k); s++) {
for (int i = 1; i <= n; i++) {
for (int mask = (s & (s - 1)); mask; mask = ((mask - 1) & s)) {
dis[s][i] = min(dis[s][i], dis[mask][i] + dis[mask ^ s][i]);
}
if (dis[s][i] < INF)
que.push(pii(dis[s][i], i));
}
Dijkstra(dis[s]);
}
printf("%d\n", dis[(1 << k) - 1][key_point[0]]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// https://www.spoj.com/problems/QTREE/en/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define lson (root << 1)
#define rson (root << 1 | 1)
const int N = 1e4 + 10;
struct Edge {
int u, v, w;
void scan() { scanf("%d%d%d", &u, &v, &w); }
} E[N];
struct SegTree {
int val[N << 2];
SegTree() {
Clear();
}
void Clear() {
memset(val, 0, sizeof(val));
}
void Update(int root, int l, int r, int pos, int v) {
if (l == r) {
val[root] = v;
return ;
}
int m = (l + r) / 2;
if (pos <= m) Update(lson, l, m, pos, v);
else Update(rson, m+1, r, pos, v);
val[root] = max(val[lson], val[rson]);
}
int Query(int root, int l, int r, int a, int b) {
if (l == a && r == b) return val[root];
int m = (l + r) / 2;
if (b <= m) return Query(lson, l, m, a, b);
else if (a > m) return Query(rson, m+1, r, a, b);
return max(Query(lson, l, m, a, m), Query(rson, m+1, r, m+1, b));
}
} bt;
vector<pii> G[N];
int fa[N], sz[N], son[N], dep[N];
int top[N], rk[N], cnt = 0;
void dfs1(int u, int f, int d) {
fa[u] = f, dep[u] = d;
son[u] = -1, sz[u] = 1;
for (const auto pir : G[u]) {
int v = pir.first;
if (v == f) continue;
dfs1(v, u, d + 1);
if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
}
}
int n;
void dfs2(int u, int t) {
top[u] = t, rk[u] = ++cnt;
if (son[u] != -1) dfs2(son[u], t);
for (const auto pir : G[u]) {
int v = pir.first;
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
for (const auto pir : G[u]) {
int v = pir.first;
if (v == fa[u]) continue;
bt.Update(1, 1, n, rk[v], pir.second);
}
}
int Query(int u, int v) {
// if (u == v) return 0;
int ans = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ans = max(ans, bt.Query(1, 1, n, rk[top[u]], rk[u]));
u = fa[top[u]];
}
if (u != v) {
if (dep[u] > dep[v]) swap(u, v);
ans = max(ans, bt.Query(1, 1, n, rk[u]+1, rk[v]));
}
return ans;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) G[i].clear();
cnt = 0, bt.Clear();
for (int i = 1; i < n; i++) {
E[i].scan();
G[E[i].u].push_back(pii(E[i].v, E[i].w));
G[E[i].v].push_back(pii(E[i].u, E[i].w));
}
dfs1(1, 0, 0);
dfs2(1, 1);
char s[10];
int a, b;
while (1) {
scanf("%s", s);
if (s[0] == 'D') break;
scanf("%d%d", &a, &b);
if (s[0] == 'C') {
int u = E[a].u, v = E[a].v;
if (u != fa[v]) swap(u, v);
assert(u == fa[v]);
bt.Update(1, 1, n, rk[v], b);
} else {
printf("%d\n", Query(a, b));
}
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) solve();
return 0;
}
// author: yang12138
// https://oi-wiki.org/graph/virtual-tree/
// https://www.luogu.com.cn/record/75047671
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5+10;
const int INF = 1e9;
int fa[N][20];
int wi[N][20];
int dep[N];
vector<pii> G[N];
int id[N], cnt = 0;
int GetLCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for (int i = 19; i >= 0; i--) {
if ((d >> i) & 1)
u = fa[u][i];
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (fa[u][i] != fa[v][i])
u = fa[u][i], v = fa[v][i];
}
return fa[u][0];
}
int GetMinWi(int f, int u) {
int d = dep[u] - dep[f];
int ans = INF;
for (int i = 19; i >= 0; i--) {
if ((d >> i) & 1) {
ans = min(ans, wi[u][i]);
u = fa[u][i];
}
}
assert(u == f);
return ans;
}
void DFS(int u, int f, int d, int w) {
fa[u][0] = f, dep[u] = d, wi[u][0] = w, id[u] = ++cnt;
for (int i = 1; i < 20; i++) {
fa[u][i] = fa[fa[u][i-1]][i-1];
wi[u][i] = min(wi[u][i-1], wi[fa[u][i-1]][i-1]);
}
for (auto [v, w1] : G[u]) {
if (v != f) DFS(v, u, d + 1, w1);
}
}
vector<pii> G2[N];
void AddEdge(int u, int v) {
G2[u].push_back(pii(v, GetMinWi(u, v)));
}
bool is[N];
ll DP(int u, vector<int>& vs) {
vs.push_back(u);
ll dp = 0;
for (auto [v, w] : G2[u]) {
ll tdp = DP(v, vs);
dp += is[v] ? w : min(1LL*w, tdp);
}
return dp;
}
int sta[N];
ll Solve(vector<int>& h) {
sort(h.begin(), h.end(), [](int a, int b) { return id[a] < id[b]; });
int top = 0;
sta[top++] = 1;
for (const int i : h) {
is[i] = 1;
assert(i != 1);
int lca = GetLCA(sta[top - 1], i);
if (lca != sta[top - 1]) {
while (id[lca] < id[sta[top - 2]]) {
AddEdge(sta[top - 2], sta[top - 1]);
top--;
}
AddEdge(lca, sta[top - 1]);
if (id[lca] != id[sta[top - 2]]) {
sta[top - 1] = lca;
} else {
top--;
}
}
sta[top++] = i;
}
for (int i = 0; i + 1 < top; i++)
AddEdge(sta[i], sta[i + 1]);
vector<int> vs;
ll ans = DP(1, vs);
for (int i : vs) G2[i].clear();
for (int i : h) is[i] = 0;
return ans;
}
void solve() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u].push_back(pii(v, w));
G[v].push_back(pii(u, w));
}
DFS(1, 0, 0, 0);
int m;
scanf("%d", &m);
while (m--) {
int k;
scanf("%d", &k);
vector<int> h(k);
for (int i = 0; i < k; i++) scanf("%d", &h[i]);
printf("%lld\n", Solve(h));
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// author: yang12138
// ref: https://oi-wiki.org/math/poly/fwt/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// C = A \oplus B
// FWT(C) = FWT(A) * FWT(B)
// sig(i & j) ^ sig(i & k) = sig(i & (j ^ k))
// xor: A'(i) = \sum_{j}((-1)^sig(i & j) * A_j)
// or: A'(i) = \sum_{i=j|i}A_j
// and: A'(i) = \sum_{i=j&i}A_j
void FWT(vector<ll>& a, int flag) {
int n = a.size();
assert((n & (n - 1)) == 0);
for (int w = 2; w <= n; w <<= 1) {
for (int i = 0; i < n; i += w) {
for (int j = i; j < i + w / 2; j++) {
ll u = a[j], v = a[j + w / 2];
if (flag == 1) {
// xor
a[j] = u + v, a[j + w / 2] = u - v;
// or
// a[j] = u, a[j + w / 2] = u + v;
// and
// a[j] = u + v, a[j + w / 2] = v;
} else {
// xor
a[j] = (u + v) / 2, a[j + w / 2] = (u - v) / 2;
// or
// a[j] = u, a[j + w / 2] = v - u;
// and
// a[j] = u - v, a[j + w / 2] = v;
}
}
}
}
}
void solve() {
srand(time(nullptr));
int n;
cin >> n;
vector<ll> a(n), b(n);
for (int i = 0; i < n; i++) a[i] = rand() % 100000;
for (int i = 0; i < n; i++) b[i] = rand() % 100000;
auto Print = [](const vector<ll>& a) {
for (ll i : a) printf("%lld ", i);
printf("\n");
};
vector<ll> c(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
c[i ^ j] += a[i] * b[j];
}
}
printf("baoli result\n");
Print(c);
FWT(a, 1);
FWT(b, 1);
vector<ll> d(n);
for (int i = 0; i < n; i++) d[i] = a[i] * b[i];
FWT(d, -1);
printf("FWT result\n");
Print(d);
bool succ = true;
for (int i = 0; i < n; i++)
succ &= (c[i] == d[i]);
printf("test %s\n", succ ? "succ" : "fail");
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// https://acm.hdu.edu.cn/showproblem.php?pid=1402
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef std::complex<double> Complex;
const double pi = acos(-1.0);
void DFT(vector<Complex>& a, const int opt) {
int n = a.size();
if (n <= 1) return ;
assert(!(n & (n - 1)));
for (int i = 0, j = 0; i < n - 1; i++) {
if (i < j) swap(a[i], a[j]);
int k = n >> 1;
while (j >= k) j -= k, k >>= 1;
j += k;
}
for (int i = 2; i <= n; i <<= 1) {
Complex wn = exp(Complex(0, opt * 2.0 * pi / i));
for (int j = 0; j < n; j += i) {
Complex w(1, 0);
for (int k = 0; k < i / 2; k++) {
Complex u = a[j + k];
Complex v = w * a[j + k + i / 2];
a[j + k] = u + v;
a[j + k + i / 2] = u - v;
w = w * wn;
}
}
}
if (opt == -1) {
for (int i = 0; i < n; i++) a[i] /= n;
}
}
vector<int> FFT(const vector<int>& a, const vector<int>& b) {
int len = 1;
while (len < max(a.size(), b.size())) len <<= 1;
len <<= 1;
vector<Complex> ca(len), cb(len);
for (int i = 0; i < a.size(); i++) ca[i] = Complex(a[i], 0);
for (int i = 0; i < b.size(); i++) cb[i] = Complex(b[i], 0);
DFT(ca, 1);
DFT(cb, 1);
vector<Complex> cc(len);
for (int i = 0; i < len; i++) cc[i] = ca[i] * cb[i];
DFT(cc, -1);
vector<int> c(len);
for (int i = 0; i < len; i++) c[i] = int(cc[i].real() + 0.5);
return c;
}
const int N = 1e6 + 10;
char s[N], t[N];
bool solve() {
if (scanf("%s%s", s, t) != 2) return false;
int n = strlen(s), m = strlen(t);
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) a[i] = s[n - 1 - i] - '0';
for (int i = 0; i < m; i++) b[i] = t[m - 1 - i] - '0';
auto c = FFT(a, b);
c.resize(c.size() + 5);
int cn = c.size();
for (int i = 1; i < cn; i++) {
c[i] += c[i - 1] / 10;
c[i - 1] %= 10;
}
bool pri = false;
for (int i = cn - 1; i >= 0; i--) {
if (pri || c[i]) {
pri = true;
printf("%d", c[i]);
}
}
if (!pri) printf("0");
printf("\n");
return true;
}
int main() {
while (solve());
return 0;
}
// https://acm.hdu.edu.cn/showproblem.php?pid=1402
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<int MOD>
struct ModInt {
public:
constexpr ModInt() {}
constexpr ModInt(int _x) : x(_x) { Ajust(); }
constexpr ModInt(ll _x) : x(_x % MOD) { Ajust(); }
constexpr inline int value() const { return x; }
constexpr inline int inv() const { return Pow(MOD - 2).value(); }
constexpr inline ModInt operator + (const ModInt& rhs) const { return ModInt(x + rhs.value()); }
constexpr inline ModInt operator - (const ModInt& rhs) const { return ModInt(x - rhs.value()); }
constexpr inline ModInt operator * (const ModInt& rhs) const { return ModInt(1LL * x * rhs.value()); }
constexpr inline ModInt operator / (const ModInt& rhs) const { return ModInt(1LL * x * rhs.inv()); }
constexpr inline ModInt operator % (const ModInt& rhs) const { return ModInt(x % rhs.value()); }
constexpr inline ModInt& operator += (const ModInt& rhs) { return (*this = ModInt(x + rhs.value())); }
constexpr inline ModInt& operator -= (const ModInt& rhs) { return (*this = ModInt(x - rhs.value())); }
constexpr inline ModInt& operator *= (const ModInt& rhs) { return (*this = ModInt(1LL * x * rhs.value())); }
constexpr inline ModInt& operator /= (const ModInt& rhs) { return (*this = ModInt(1LL * x * rhs.inv())); }
constexpr inline ModInt& operator %= (const ModInt& rhs) { return (*this = ModInt(x % rhs.value())); }
ModInt Pow(ll n) const {
ll ans = 1, p = x;
while (n) {
if (n & 1) ans = ans * p % MOD;
p = p * p % MOD;
n >>= 1;
}
return ModInt(ans);
}
private:
constexpr inline void Ajust() {
if (x >= 2 * MOD || x < -MOD) x %= MOD;
if (x >= MOD) x -= MOD;
else if (x < 0) x += MOD;
}
int x = 0;
};
constexpr int MOD = 998244353;
typedef ModInt<MOD> mint;
constexpr mint g = 3;
void DFT(vector<mint>& a, int opt) {
int n = a.size();
if (n <= 1) return ;
assert(!(n & (n - 1)));
for (int i = 0, j = 0; i < n - 1; i++) {
if (i < j) swap(a[i], a[j]);
int k = n / 2;
while (j >= k) j -= k, k /= 2;
j += k;
}
for (int i = 2; i <= n; i <<= 1) {
mint wn = g.Pow(1LL * (MOD - 1) / i * ((opt < 0) ? (MOD - 2) : 1));
for (int j = 0; j < n; j += i) {
mint w = 1;
for (int k = j; k < j + i / 2; k++) {
mint u = a[k], v = w * a[k + i / 2];
a[k] = u + v, a[k + i / 2] = u - v;
w *= wn;
}
}
}
if (opt < 0) {
mint invn = mint(n).inv();
for (int i = 0; i < n; i++) a[i] *= invn;
}
}
const int N = 1e6 + 10;
char s[N], t[N];
bool solve() {
if (scanf("%s%s", s, t) != 2) return false;
int n = strlen(s), m = strlen(t);
int len = 1;
while (len < n + m - 1) len <<= 1;
vector<mint> a(len), b(len);
for (int i = 0; i < n; i++) a[n - 1 - i] = s[i] - '0';
for (int i = 0; i < m; i++) b[m - 1 - i] = t[i] - '0';
DFT(a, 1);
DFT(b, 1);
for (int i = 0; i < len; i++) a[i] *= b[i];
DFT(a, -1);
a.resize(a.size() + 5);
for (int i = 1; i < a.size(); i++) {
a[i] += a[i - 1].value() / 10;
a[i - 1] %= 10;
}
bool pri = false;
for (int i = a.size() - 1; i >= 0; i--) {
if (pri || a[i].value() || i == 0) {
printf("%d", a[i].value());
pri = true;
}
}
printf("\n");
return true;
}
int main() {
while (solve());
return 0;
}
// http://acm.hdu.edu.cn/showproblem.php?pid=3579
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
void AddMod(ll& a, ll b, ll mod) {
a += b;
if (a >= mod) a -= mod;
}
ll MulMod(ll a, ll b, ll mod) {
a %= mod, b %= mod;
if (a > b) swap(a, b);
ll ans = 0;
while (a) {
if (a & 1) AddMod(ans, b, mod);
AddMod(b, b, mod);
a >>= 1;
}
return ans;
}
void Exgcd(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1, y = 0;
} else {
Exgcd(b, a % b, x, y);
// b*x+(a%b)*y = 1
// b*x+(a-a/b*b)*y=1
// b*(x-a/b*y)+a*y=1
ll t = y;
y = x - a / b * y;
x = t;
}
}
ll MulInv(ll a, ll mod) {
a %= mod;
ll x, y;
Exgcd(a, mod, x, y);
assert(a * x + mod * y == 1);
x %= mod;
if (x < 0) x += mod;
return x;
}
ll ChineseRemainderTheorem(const vii& mods, const vii& xs) {
assert(mods.size() == xs.size() && mods.size());
const int n = mods.size();
ll M = 1;
for (const ll mod : mods) M *= mod;
ll ans = 0;
for (int i = 0; i < n; i++) {
ll mi = M / mods[i];
AddMod(ans, MulMod(mi * MulInv(mi, mods[i]), xs[i], M), M);
}
return ans;
}
ll ChineseRemainderTheoremCoprimeVersion(const vii& mods, const vii& xs) {
auto Process = [](ll x1, ll mod1, ll x2, ll mod2, ll& x, ll& mod) -> bool {
ll g = __gcd(mod1, mod2);
if ((x1 - x2) % g) return false;
mod1 /= g, mod2 /= g;
mod = mod1 * mod2 * g;
x = MulMod(x2 - x1 + mod, MulInv(mod1, mod2) * mod1, mod);
AddMod(x, x1, mod);
return true;
};
assert(mods.size() == xs.size() && mods.size());
const int n = mods.size();
ll x = xs[0], mod = mods[0];
for (int i = 1; i < n; i++) {
if (!Process(x, mod, xs[i], mods[i], x, mod)) return -1;
}
if (x == 0) x = mod;
return x;
}
ll solve() {
int n;
scanf("%d", &n);
vii mods(n), xs(n);
for (int i = 0; i < n; i++)
scanf("%lld", &mods[i]);
for (int i = 0; i < n; i++)
scanf("%lld", &xs[i]);
return ChineseRemainderTheoremCoprimeVersion(mods, xs);
}
int main() {
int T = 1, t = 0;
scanf("%d", &T);
while (T--) {
printf("Case %d: %lld\n", ++t, solve());
}
return 0;
}
// http://acm.hdu.edu.cn/showproblem.php?pid=5901
// author: yang12138
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
namespace primecount {
// 240MB
const int N = 70000;
const int M = 700;
const int PM = 1e7 + 10;
int phi[N][M];
int p[PM / 20], pcnt = 0;
int pc[PM];
void init() {
for (int i = 2; i < PM; i++) {
if (!pc[i]) p[++pcnt] = i;
for (int j = 1; j <= pcnt; j++) {
int u = i * p[j];
if (u >= PM) break;
pc[u] = 1;
if (i % p[j] == 0) break;
}
}
for (int i = 1; i < N; i++) phi[i][0] = i - 1;
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
phi[i][j] = phi[i][j-1];
if (i >= p[j] * p[j])
phi[i][j] -= phi[i / p[j]][j-1] - (j - 1);
}
}
for (int i = 2; i < PM; i++)
pc[i] = pc[i-1] + !pc[i];
}
ll Phi(ll n, int m) {
if (n <= 1) return 0;
if (n < N && m < M) return phi[n][m];
if (m == 0) return n - 1;
ll ans = Phi(n, m - 1);
if (n / p[m] >= p[m]) {
ans -= Phi(n / p[m], m - 1) - (m - 1);
}
return ans;
}
int Sqrt(ll n) {
int k = sqrt(n + 0.01);
while (1LL * k * k > n) k--;
while (1LL * (k + 1) * (k + 1) <= n) k++;
return k;
}
int Cbrt(ll n) {
int k = cbrt(n + 0.01);
while (1LL * k * k * k > n) k--;
while (1LL * (k + 1) * (k + 1) * (k + 1) <= n) k++;
return k;
}
// 2 ~ n
// 1e11 350ms
// 1e12 2s
ll PrimeCount(ll n) {
if (n < PM) return pc[n];
int a = pc[Sqrt(n)], b = pc[Cbrt(n)];
ll ans = Phi(n, b);
for (int i = b + 1; i <= a; i++) {
ans -= PrimeCount(n / p[i]);
}
ans += 1LL * b * (a - b) + 1LL * (a - b) * (a - b - 1) / 2;
return ans;
}
} // namespace primecount
void solve() {
ll n;
scanf("%lld", &n);
printf("%lld\n", primecount::PrimeCount(n));
}
int main() {
primecount::init();
int T = 1;
scanf("%d", &T);
while (T--) solve();
return 0;
}
// http://acm.hdu.edu.cn/showproblem.php?pid=6248
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const double eps = 1e-8;
const double inf = 1e18;
int dcmp(const double x) {
return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1);
}
/*
target = v + sum(c_i*x_i), i in non_basic
x_i = b_i - sum(A_{ij}*x_j), i in basic, j in non_basic
*/
struct Simplex {
public:
Simplex(int n, int m): n(n), m(m), size(n + m + 2), A(size, vector<double>(size, 0)), x(size, 0) {
for (int i = 1; i <= n; i++) non_basic.insert(i);
for (int i = 1; i <= m; i++) basic.insert(n + i);
}
~Simplex() {}
// variable 1 ~ n
// restrict n + 1 ~ n + m
void AddRestricts(const vector<vector<double>>& restricts) {
assert(restricts.size() == m);
assert(restricts[0].size() == n + 1);
for (int i = 0; i < m; i++) {
for (int j = 0; j <= n; j++) {
A[1 + n + i][j] = restricts[i][j];
}
}
}
void SetTarget(const vector<double>& target) {
assert(target.size() == n + 1);
for (int i = 0; i <= n; i++) A[0][i] = target[i];
}
const vector<double>& GetVariable() { return x; }
double GetAns() { return A[0][0]; }
// -1 no answer, -2 unlimited answer, 0 nomral answer
int Run() {
// print();
if (!Fesible()) {
// printf("fuck, infesible\n");
const auto real_target = A[0];
std::fill(A[0].begin(), A[0].end(), 0);
// target = -x_0
// x_i = b_i - sum(A_{ij}*x_j) + x_0
A[0][size - 1] = -1;
int idx = -1;
for (const int i : basic) {
A[i][size - 1] = -1;
if (idx == -1 || A[i][0] < A[idx][0]) idx = i;
}
non_basic.insert(size - 1);
Pivot(size - 1, idx);
assert(Fesible());
RunSimplex();
if (dcmp(x[size - 1]) != 0) return -1;
if (basic.count(size - 1)) {
for (const int i : non_basic) {
if (dcmp(A[size - 1][i]) != 0) {
Pivot(i, size - 1);
break;
}
}
}
non_basic.erase(size - 1);
A[0] = real_target;
for (const int i : basic) {
if (dcmp(A[0][i]) != 0) {
for (const int j : non_basic) {
A[0][j] -= A[0][i] * A[i][j];
}
A[0][0] += A[0][i] * A[i][0];
}
}
}
assert(Fesible());
// print();
return RunSimplex();
}
void print() const {
printf("target = %.3f + ", A[0][0]);
bool start = true;
for (const int j : non_basic) {
if (!start) printf(" + ");
start = false;
printf("%.3f*x(%d)", A[0][j], j);
}
printf("\n");
for (const int i : basic) {
printf("x(%d) = %.3f - (", i, A[i][0]);
bool start = true;
for (const int j : non_basic) {
if (!start) printf(" + ");
start = false;
printf("%.3f*x(%d)", A[i][j], j);
}
printf(")\n");
}
printf("\n");
}
private:
const int n, m, size;
vector<vector<double>> A;
vector<double> x;
std::set<int> basic, non_basic;
// e nonbasic, l basic
void Pivot(int e, int l) {
assert(dcmp(A[l][e]) != 0);
// printf("Pivot e %d, l %d\n", e, l);
A[e][0] = A[l][0] / A[l][e];
for (const int i : non_basic) {
if (i == e) continue;
A[e][i] = A[l][i] / A[l][e];
}
A[e][l] = 1.0 / A[l][e];
for (const int i : basic) {
if (i == l) continue;
A[i][0] -= A[i][e] * A[e][0];
for (const int j : non_basic) {
if (j == e) continue;
A[i][j] -= A[i][e] * A[e][j];
}
A[i][l] = -A[i][e] * A[e][l];
}
A[0][0] += A[0][e] * A[e][0];
for (const int i : non_basic) {
if (i == e) continue;
A[0][i] -= A[0][e] * A[e][i];
}
A[0][l] = -A[0][e] * A[e][l];
non_basic.erase(e), non_basic.insert(l);
basic.erase(l), basic.insert(e);
}
int Choose(int& e, int& l) {
e = l = -1;
for (const int i : non_basic) {
if (dcmp(A[0][i]) > 0) {
e = i;
break;
}
}
if (e == -1) return -1;
for (const int i : basic) {
if (dcmp(A[i][e]) > 0) {
if (l == -1 || dcmp(A[i][0] / A[i][e] - A[l][0] / A[l][e]) < 0) {
l = i;
}
}
}
if (l == -1) return -2;
return 0;
}
int RunSimplex() {
int e = -1, l = -1, ret = 0;
do {
ret = Choose(e, l);
// printf("Choose ret %d, e %d, l %d\n", ret, e, l);
if (ret == -1) {
// finish
for (const int i : non_basic) x[i] = 0;
for (const int i : basic) x[i] = A[i][0];
ret = 0;
break;
} else if (ret == -2) {
// unlimited answer
for (const int i : non_basic) x[i] = 0;
for (const int i : basic) x[i] = 0;
x[e] = inf;
} else {
// ret == 0
Pivot(e, l);
}
} while (ret == 0);
return ret;
}
bool Fesible() const {
for (const int i : basic) {
if (dcmp(A[i][0]) < 0) return false;
}
return true;
}
};
void solve(const int cas) {
int n, m;
scanf("%d%d", &n, &m);
vector<int> a(n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
vector<int> idx(1 << n, 0);
int cnt = 0;
for (int i = 0; i < (1 << n); i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
sum += ((i >> j) & 1) * a[j];
}
if (sum <= m) idx[i] = ++cnt;
}
int v = cnt, e = 2 * n;
Simplex solver(v, e);
vector<vector<double>> restricts(e, vector<double>(v + 1));
vector<double> target(v + 1);
restricts[0][0] = 1.0;
for (int i = 1; i <= v; i++) restricts[0][i] = 1.0;
restricts[1][0] = -1.0;
for (int i = 1; i <= v; i++) restricts[1][i] = -1.0;
for (int i = 0; i + 1 < n; i++) {
for (int mask = 0; mask < (1 << n); mask++) {
if (((mask >> i) & 1) && idx[mask]) {
restricts[2*i+2][idx[mask]] += 1.0;
restricts[2*i+3][idx[mask]] -= 1.0;
if (i == 0) {
target[idx[mask]] = 1.0;
}
}
if (((mask >> (i + 1)) & 1) && idx[mask]) {
restricts[2*i+2][idx[mask]] -= 1.0;
restricts[2*i+3][idx[mask]] += 1.0;
}
}
}
for (int mask = 0; mask < (1 << n); mask++) {
if (((mask >> 0) & 1) && idx[mask]) {
target[idx[mask]] = 1.0;
}
}
solver.AddRestricts(restricts);
solver.SetTarget(target);
solver.Run();
printf("Case #%d: %.8f\n", cas, max(0.0, solver.GetAns()));
}
int main() {
int T = 1, t = 0;
scanf("%d", &T);
while (T--) solve(++t);
return 0;
}
// http://www.51nod.com/Challenge/Problem.html#problemId=1549
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
const double eps = 1e-8;
int Gauss(vector<vector<double>> x, vector<double>& ans) {
int n = x.size();
for (int i = 0; i < n; i++) {
int p = i;
for (int j = i+1; j < n; j++)
if (fabs(x[j][i]) > fabs(x[p][i])) p = j;
if (fabs(x[p][i]) < eps) return -1;
swap(x[i], x[p]);
for (int j = 0; j < n; j++) {
if (i == j) continue;
double factor = x[j][i] / x[i][i];
for (int k = i; k <= n; k++) {
x[j][k] -= x[i][k] * factor;
}
}
}
ans.resize(n);
for (int i = 0; i < n; i++) {
ans[i] = x[i][n] / x[i][i];
for (int j = 0; j < n; j++) {
assert(i == j || fabs(x[i][j]) < eps);
}
}
return 0;
}
void solve() {
// star <= 10 -> 不掉星
// 连胜三局 && star <= 70 -> extra star
int from;
double p;
cin >> from >> p;
int n = 97;
vector<vector<double>> x(3*n, vector<double>(3*n+1, 0.0));
auto ID = [](int star, int win) {
return win * 97 + star;
};
int tot = 3*n;
for (int star = 0; star <= 95; star++) {
for (int win = 0; win <= 2; win++) {
int row = ID(star, win);
x[row][row] = 1.0;
x[row][tot] = 1.0;
if (win == 2 && star <= 70) {
x[row][ID(star+2, 2)] -= p;
} else {
x[row][ID(star+1, min(2, win+1))] -= p;
}
if (star <= 10) {
x[row][ID(star, 0)] -= 1.0-p;
} else {
x[row][ID(max(0, star-1), 0)] -= 1.0-p;
}
}
}
x[ID(96, 0)][ID(96, 0)] = 1.0;
x[ID(96, 1)][ID(96, 1)] = 1.0;
x[ID(96, 2)][ID(96, 2)] = 1.0;
vector<double> ans;
int ret = Gauss(x, ans);
assert(ret == 0);
printf("%.10f\n", ans[ID(96-from, 0)]);
}
int main() {
solve();
return 0;
}
// http://acm.hdu.edu.cn/showproblem.php?pid=3949
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vii;
const int B = 60;
bool Contain(ll v, int b) { return (v >> b) & 1; }
vii LinearBasis(vii v) {
vii ans;
for (int i = B - 1, r = 0; i >= 0 && r < v.size(); i--) {
int pos = -1;
for (int j = r; j < v.size(); j++) {
if (Contain(v[j], i)) { pos = j; break; }
}
if (pos == -1) continue;
swap(v[r], v[pos]);
for (int j = r + 1; j < v.size(); j++)
if (Contain(v[j], i)) v[j] ^= v[r];
for (ll& t : ans)
if (Contain(t, i)) t ^= v[r];
ans.push_back(v[r++]);
}
return ans;
}
void print(ll v) {
for (int i = B - 1; i >= 0; i--) {
printf("%d", Contain(v, i) ? 1 : 0);
}
printf("\n");
}
void solve() {
int n;
scanf("%d", &n);
vii v(n);
for (int i = 0; i < n; i++) scanf("%lld", &v[i]);
vii v2 = LinearBasis(v);
bool sub = v2.size() < v.size();
// for (auto i : v2) print(i);
int Q;
scanf("%d", &Q);
while (Q--) {
ll k;
scanf("%lld", &k);
k -= sub;
if (k == 0) {
printf("0\n");
continue;
}
if (k >= (1LL << v2.size())) {
printf("-1\n");
continue;
}
ll ans = 0;
for (int i = 0; i < v2.size(); i++) {
if (Contain(k, i)) ans ^= v2.end()[-i-1];
}
printf("%lld\n", ans);
}
}
int main() {
int T = 1, t = 0;
scanf("%d", &T);
while (T--) {
printf("Case #%d:\n", ++t);
solve();
}
return 0;
}
// http://www.51nod.com/Challenge/Problem.html#problemId=1232
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 2520;
ll dp[20][MOD + 1][50];
int idx[MOD + 1];
int c[MOD + 1][10];
int num[20];
ll DP(int len, int left, int lcm, bool flag) {
if (len == 0) return lcm && (left % lcm == 0);
ll& tdp = dp[len][left][idx[lcm]];
if (flag && tdp >= 0) return tdp;
ll ans = 0;
for (int i = flag ? 9 : num[len]; i >= 0; i--) {
ans += DP(len-1, (left*10+i) % MOD , c[lcm][i], flag || (i < num[len]));
}
if (flag) tdp = ans;
return ans;
}
ll CalcAns(ll n) {
if (n <= 0) return 0;
int len = 0;
while (n) {
num[++len] = n % 10;
n /= 10;
}
return DP(len, 0, 0, 0);
}
void solve() {
int cnt = 0;
idx[0] = cnt++;
for (int i = 1; i <= MOD; i++)
if (MOD % i == 0) idx[i] = cnt++;
// cout << cnt << endl;
c[0][0] = 0;
for (int i = 1; i <= 9; i++) c[0][i] = i;
for (int i = 1; i <= MOD; i++) {
c[i][0] = i;
for (int j = 1; j <= 9; j++) {
c[i][j] = i * j / __gcd(i, j);
}
}
int Q;
scanf("%d", &Q);
while (Q--) {
ll l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", CalcAns(r) - CalcAns(l - 1));
}
}
int main() {
memset(dp, -1, sizeof(dp));
int T = 1;
// scanf("%d", &T);
while (T--) solve();
return 0;
}
// https://leetcode.cn/contest/autox2023/problems/TcdlJS/
class Solution {
public:
typedef long long ll;
struct Line {
ll x1, y1, x2, y2;
Line(ll x1, ll y1, ll x2, ll y2) : x1(x1), y1(y1), x2(x2), y2(y2) {
// if (x1 > x2) swap(x1, x2), swap(y1, y2);
// else if (x1 == x2 && y1 > y2) swap(y1, y2);
}
array<ll, 3> Get() const {
// y-y1 = (y2-y1)/(x2-x1)*(x-x1)
// (y-y1)*(x2-x1)=(y2-y1)*(x-x1)
ll a = (y2-y1), b = (x1-x2), c = -x1*(y2-y1)+y1*(x2-x1);
ll g = __gcd(a, __gcd(b, c));
a /= g, b /= g, c /= g;
if (a < 0) a = -a, b = -b, c = -c;
else if (a == 0 && b < 0) b = -b, c = -c;
return {a, b, c};
}
bool Contain(ll x, ll y) const {
return x >= min(x1, x2) && x <= max(x1, x2) && y >= min(y1, y2) && y <= max(y1, y2);
}
bool Inter(const Line& rhs) const {
auto l = Get(), r = rhs.Get();
if (l[0]*r[1] == r[0]*l[1]) {
if (l[0] == r[0] && l[1] == r[1] && l[2] == r[2]) {
return Contain(rhs.x1, rhs.y1) || Contain(rhs.x2, rhs.y2) || rhs.Contain(x1, y1) || rhs.Contain(x2,y2);
}
return false;
}
if (r[0] == 0) swap(l, r);
assert(r[0]);
double y = 1.0 * (l[0]*r[2]-r[0]*l[2]) / (r[0]*l[1] - l[0]*r[1]);
double x = 1.0 * (-r[2]-r[1]*y)/r[0];
static const double eps = 1e-8;
if (y > min(y1, y2) - eps && y < max(y1, y2) + eps &&
y > min(rhs.y1, rhs.y2) - eps && y < max(rhs.y1, rhs.y2) + eps &&
x > min(x1, x2) - eps && x < max(x1, x2) + eps &&
x > min(rhs.x1, rhs.x2) - eps && x < max(rhs.x1, rhs.x2) + eps)
return true;
return false;
}
};
struct Circle {
ll x, y, r;
Circle(ll x, ll y, ll r) : x(x), y(y), r(r) {}
bool Contain(const Circle& rhs) const {
return (x-rhs.x)*(x-rhs.x)+(y-rhs.y)*(y-rhs.y) < (r-rhs.r)*(r-rhs.r);
}
bool Separated(const Circle& rhs) const {
return (x-rhs.x)*(x-rhs.x)+(y-rhs.y)*(y-rhs.y) > (r+rhs.r)*(r+rhs.r);
}
bool Inter(const Circle& rhs) const {
if (Contain(rhs) || rhs.Contain(*this) || Separated(rhs)) return false;
return true;
}
static int sig(ll x) { return x == 0 ? 0 : (x < 0 ? -1 : 1); }
bool Inter(const Line& rhs) const {
ll d1 = (x-rhs.x1)*(x-rhs.x1)+(y-rhs.y1)*(y-rhs.y1) - r*r;
ll d2 = (x-rhs.x2)*(x-rhs.x2)+(y-rhs.y2)*(y-rhs.y2) - r*r;
if (sig(d1)*sig(d2) <= 0) return true;
if (d1 < 0 && d2 < 0) return false;
ll a1 = rhs.x2-rhs.x1, b1 = rhs.y2-rhs.y1, c1 = x*(rhs.x1-rhs.x2)+y*(rhs.y1-rhs.y2);
ll a2 = rhs.y2-rhs.y1, b2 = rhs.x1-rhs.x2, c2 = rhs.x1*(rhs.y1-rhs.y2)+rhs.y1*(rhs.x2-rhs.x1);
if (a2 == 0) swap(a1, a2), swap(b1, b2), swap(c1, c2);
assert(a2);
double y0 = 1.0 * (a1*c2-a2*c1) / (a2*b1-a1*b2);
// printf("y0 %.5f, y1 %lld, y2 %lld\n", y0, rhs.y1, rhs.y2);
static const double eps = 1e-8;
if (y0 > min(rhs.y1, rhs.y2) - eps && y0 < max(rhs.y1, rhs.y2) + eps) {
double x0 = 1.0*(-c2-b2*y0)/a2;
// printf("%.10f %.10f\n", x0, y0);
if ((x-x0)*(x-x0)+(y-y0)*(y-y0) < r*r+eps) return true;
}
return false;
}
};
void dfs(int u, const vector<vector<int>>& vis, vector<int>& id, int tmp) {
id[u] = tmp;
for (int i = 0; i < vis.size(); i++) {
if (vis[u][i] && id[i] < 0) {
dfs(i, vis, id, tmp);
}
}
}
vector<bool> antPass(vector<vector<int>>& g, vector<vector<int>>& path) {
int n = g.size();
vector<pair<Line, int>> lines;
vector<pair<Circle, int>> cirs;
for (int i = 0; i < n; i++) {
const auto& v = g[i];
if (v.size() == 4) {
Line line(v[0], v[1], v[2], v[3]);
lines.emplace_back(line, i);
} else if (v.size() == 3) {
Circle cir(v[0], v[1], v[2]);
cirs.emplace_back(cir, i);
} else {
assert(false);
}
}
vector<vector<int>> vis(n, vector<int>(n, 0));
for (const auto& [l1, i] : lines) {
for (const auto& [l2, j] : lines) {
vis[i][j] = l1.Inter(l2);
}
}
for (const auto& [c1, i] : cirs) {
for (const auto& [c2, j] : cirs) {
vis[i][j] = c1.Inter(c2);
}
}
for (const auto& [l, i] : lines) {
for (const auto& [c, j] : cirs) {
vis[i][j] = vis[j][i] = c.Inter(l);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
assert(vis[i][j] == vis[j][i]);
// printf("%d %d %d\n", i, j, vis[i][j]);
}
}
vector<int> id(n, -1);
int tmp = 0;
for (int i = 0; i < n; i++) {
if (id[i] < 0) {
dfs(i, vis, id, tmp++);
}
}
vector<bool> ans;
for (auto& q : path) {
if (id[q[0]] == id[q[1]]) ans.push_back(true);
else ans.push_back(false);
}
return ans;
}
};
// https://acm.hdu.edu.cn/showproblem.php?pid=5412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 3e5+10;
struct Bits {
int bits[N], n;
void Reset(int n) {
std::fill(bits, bits + n + 1, 0);
this->n = n;
}
void Add(int i, int d) {
while (i <= n) {
bits[i] += d;
i += i & -i;
}
}
int Sum(int i) {
int ans = 0;
while (i) {
ans += bits[i];
i -= i & -i;
}
return ans;
}
} bt;
struct Query {
int op;
int l, r, k, id;
int flag;
void scan(int id) {
scanf("%d", &op);
if (op == 1) scanf("%d%d", &l, &k);
else scanf("%d%d%d", &l, &r, &k);
this->id = id;
flag = 1;
}
} Q[N], Q1[N], Q2[N];
int ans[N], tmp[N];
void solve(int l, int r, int a, int b) {
if (a > b) return ;
if (l == r) {
for (int i = a; i <= b; i++) {
if (Q[i].op == 2)
ans[Q[i].id] = l;
}
return ;
}
int m = (l + r) >> 1;
for (int i = a; i <= b; i++) {
if (Q[i].op == 1 && Q[i].k <= m) {
bt.Add(Q[i].l, Q[i].flag);
} else if (Q[i].op == 2) {
tmp[i] = bt.Sum(Q[i].r) - bt.Sum(Q[i].l-1);
}
}
for (int i = a; i <= b; i++) {
if (Q[i].op == 1 && Q[i].k <= m) {
bt.Add(Q[i].l, -Q[i].flag);
}
}
int t1 = 0, t2 = 0;
for (int i = a; i <= b; i++) {
if (Q[i].op == 1) {
if (Q[i].k <= m) Q1[t1++] = Q[i];
else Q2[t2++] = Q[i];
} else {
if (tmp[i] >= Q[i].k) Q1[t1++] = Q[i];
else {
Q2[t2++] = Q[i];
Q2[t2-1].k -= tmp[i];
}
}
}
assert(a + t1 + t2 - 1 == b);
for (int i = a; i < a + t1; i++) Q[i] = Q1[i-a];
for (int i = a + t1; i < a + t1 + t2; i++) Q[i] = Q2[i-a-t1];
solve(l, m, a, a + t1 - 1);
solve(m+1, r, a + t1, a + t1 + t2 - 1);
}
int b[N], m;
int pre[N], n;
int GetRank(int x) {
return lower_bound(b+1, b+m+1, x) - b;
}
bool solve() {
if (scanf("%d", &n) != 1) return false;
m = 0;
int tn = 0;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
auto& query = Q[++tn];
query.op = 1, query.l = i, query.k = x, query.flag = 1;
b[++m] = x;
pre[query.l] = x;
}
int q;
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
auto& query = Q[++tn];
query.scan(i);
if (query.op == 1) {
b[++m] = query.k;
auto& query2 = Q[++tn];
query2 = query;
query2.k = pre[query.l];
query2.flag = -1;
pre[query.l] = query.k;
swap(query, query2);
}
}
sort(b+1, b+m+1);
// m = unique(b+1, b+m+1)-b-1;
for (int i = 1; i <= tn; i++)
if (Q[i].op == 1)
Q[i].k = GetRank(Q[i].k);
bt.Reset(n);
std::fill(ans+1, ans+q+1, -1);
solve(1, m, 1, tn);
for (int i = 1; i <= q; i++) {
if (ans[i] > 0) printf("%d\n", b[ans[i]]);
}
return true;
}
int main() {
while (solve());
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct FastIO {
static const int BUFFER_SIZE = (1 << 24);
char buffer[BUFFER_SIZE];
char *head = nullptr, *tail = nullptr;
void ReadBuffer() {
int len = fread(buffer, 1, BUFFER_SIZE, stdin);
head = buffer, tail = buffer + len;
}
char getch() {
if (head == tail) ReadBuffer();
if (head == tail) return 0;
return *head++;
}
template<class T>
void Read(T& n) {
n = 0;
bool flag = false;
char ch = getch();
while (!isdigit(ch) && ch != '-') ch = getch();
if (ch == '-') flag = true, ch = getch();
do {
n = 10 * n + ch - '0';
ch = getch();
} while (isdigit(ch));
if (flag) n = -n;
}
template<class T>
void Print(const T n) const {
if (n < 0) {
putchar('-');
Print(-n);
return ;
}
if (n > 9) Print(n / 10);
putchar(n % 10 + '0');
}
} io;
void solve() {
int n;
io.Read(n);
io.Print(n);
printf("\n");
while (n--) {
ll x;
io.Read(x);
io.Print(x);
printf("\n");
}
}
void solve2() {
int n;
scanf("%d", &n);
printf("%d\n", n);
while (n--) {
ll x;
scanf("%lld", &x);
printf("%lld\n", x);
}
}
int main(int argc, char** argv) {
int t = atoi(argv[1]);
if (t == 1) solve();
else solve2();
return 0;
}
set nu
syntax on
set autoindent
set cindent
set cursorline
set mouse=a
set ts=4
set expandtab
set shiftwidth=4
set hlsearch
set ignorecase
if has("autocmd")
au BufReadPost * if line("'\"") > 1 && line("'\"") <= line("$") | exe "normal! g'\"" | endif
endif