emanual20

Github: @Emanual20 南开大学知名校友 graduate of nku

5671

_marble_
wxzcch

JJ0k_12
tinker
xzx_123
lsz_
Twinkle_wuwu
cy._1

jjj_k
I-_-I

YottaByte_7

762174555

## 题面

- “1 u v” 表示从u到v添加一条边
- “2 x” 打印从x可达的最小节点编号

($n \le 2e5, q \le 2e5$)

## 题意

- 1. 将所有$A_i==0$的元素随机替换为某个均匀分布X~U(1, M)中的整数元素
- 2. 将数组A按升序排序

($1\le K \le N \le 2e3, 1 \le M \le 2e3, 0 \le A_i \le M$)

emanual20
10天前

# G - Distance Queries on a Tree

### 题意

• 1 i w: 表示把第i条边的权重改为w
• 2 u v: 询问从节点u到v的距离

($n \le 2e5, w_i, w \le 1e9, q \le 2e5$)

### 题解

$$dist(u, v) = dist(u, root) + dist(v, root) - 2dist(lca(u, v), root)$$

/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2023-3-22
*
*
*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;

const ll MOD = 1e9 + 7;
int n, root, q;
vector<int> edges[maxn];

struct item{
int nto, nw, nidx;
};
vector<item> ne[maxn];
int idx2dnode[maxn];

#define lson(x) ((x) << 1)
#define rson(x) ((x) << 1 | 1)
#define father(x) ((x) >> 1)

struct seg_node{
int left, right;
ll sum, lazy;
};

struct HeavyLightNode{
int fath, heavyson, top;
int sz, depth;
int w, seq;
} a[maxn];

struct HeavyLightDecomposition{
public:
int Timestamp, ts2orindex[maxn];
seg_node tree[4 * maxn];
public:
void init(){
Timestamp = 0, memset(ts2orindex, 0, sizeof(ts2orindex));
}

void dfs1(int now, int fm, int depth){
a[now].fath = fm, a[now].depth = depth, a[now].sz = 1;
for(auto &it : edges[now]){
if(it != fm){
dfs1(it, now, depth + 1);
a[now].sz += a[it].sz;
if(a[it].sz > a[a[now].heavyson].sz)
a[now].heavyson = it;
}
}
}

void dfs2(int now, int fm, int tp){
Timestamp += 1, a[now].seq = Timestamp, ts2orindex[Timestamp] = now, a[now].top = tp;
// if node now haven't any heavy sons, return
if(!a[now].heavyson) return;
dfs2(a[now].heavyson, now, tp);
for(auto &it : edges[now]){
if(it != fm && it != a[now].heavyson){
// light node is the first node of any chain
dfs2(it, now, it);
}
}
}

void Pushup(int k){
tree[k].sum = tree[lson(k)].sum + tree[rson(k)].sum;
}

void build_seg(int left, int right, int k = 1){
tree[k].left = left, tree[k].right = right;
if (left == right){
tree[k].sum = a[ts2orindex[left]].w;
return;
}
int mid = (left + right) >> 1;
build_seg(left, mid, lson(k));
build_seg(mid + 1, right, rson(k));
Pushup(k);
}

void Pushdown(int k){
if (tree[k].lazy == 0) return;
tree[lson(k)].lazy += tree[k].lazy, tree[rson(k)].lazy += tree[k].lazy;
tree[lson(k)].lazy %= MOD, tree[rson(k)].lazy %= MOD;
tree[lson(k)].sum += tree[k].lazy * (tree[lson(k)].right - tree[lson(k)].left + 1);
tree[lson(k)].sum %= MOD;
tree[rson(k)].sum += tree[k].lazy * (tree[rson(k)].right - tree[rson(k)].left + 1);
tree[rson(k)].sum %= MOD;
tree[k].lazy = 0;
}

void Update_seg(int l, int r, int x, int y, ll C, int k = 1){
if (x <= l && r <= y){
tree[k].sum = C, tree[k].sum %= MOD;
return;
}
Pushdown(k);
int mid = (l + r) >> 1;
if(x <= mid) Update_seg(l, mid, x, y, C, lson(k));
if(y > mid) Update_seg(mid + 1, r, x, y, C, rson(k));
Pushup(k);
}

ll Query_seg(int l, int r, int x, int y, int k = 1){
ll ret = 0;
if (x <= l && r <= y){
ret = tree[k].sum;
return ret;
}
Pushdown(k);
int mid = (l + r) >> 1;
if (mid >= x) ret += Query_seg(l, mid, x, y, lson(k));
if (mid < y) ret += Query_seg(mid + 1, r, x, y, rson(k));
return ret;
}

Update_seg(1, n, a[u].seq, a[u].seq + a[u].sz - 1, k);
}

ll QuerySubtree(int u){
return Query_seg(1, n, a[u].seq, a[u].seq + a[u].sz - 1);
}

void UpdatePath(int u, int v, ll k){
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
Update_seg(1, n, a[a[u].top].seq, a[u].seq, k);
u = a[u].top;
u = a[u].fath;
}
if(a[u].depth < a[v].depth)
swap(u, v);
Update_seg(1, n, a[v].seq, a[u].seq, k);
}

ll QueryPath(int u, int v){
ll ret = 0;
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
ret += Query_seg(1, n, a[a[u].top].seq, a[u].seq);
u = a[u].top;
u = a[u].fath;
}
if(a[u].depth < a[v].depth)
swap(u, v);
ret += Query_seg(1, n, a[v].seq, a[u].seq);
return ret;
}

ll QueryLCA(int u, int v){
while(a[u].top != a[v].top){
if(a[a[u].top].depth < a[a[v].top].depth)
swap(u, v);
u = a[a[u].top].fath;
}
return a[u].depth < a[v].depth ? u : v;
}
};

void dfs_init(int now, int fm){
for(auto &it : ne[now]){
auto nto = it.nto, nw = it.nw, nidx = it.nidx;
if(nto != fm){
a[nto].w = nw, idx2dnode[nidx] = nto;
dfs_init(nto, now);
}
}
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

cin >> n;
for (int i = 1; i < n; i++){
int nfm, nto, nw;
cin >> nfm >> nto >> nw;
edges[nfm].push_back(nto), edges[nto].push_back(nfm);
ne[nfm].push_back({nto, nw, i}), ne[nto].push_back({nfm, nw, i});
}

root = 1;
dfs_init(1, -1);
HeavyLightDecomposition hld;
hld.init();
hld.dfs1(root, -1, 1);
hld.dfs2(root, -1, root);
hld.build_seg(1, n);

cin >> q;
while(q--){
int op;
cin >> op;
if(op == 1){
int nidx, nw;
cin >> nidx >> nw;
hld.UpdatePath(idx2dnode[nidx], idx2dnode[nidx], nw);
}
else if(op == 2){
int nu, nv;
cin >> nu >> nv;
auto res = hld.QueryPath(root, nu) + hld.QueryPath(root, nv) - 2 * hld.QueryPath(root, hld.QueryLCA(nu, nv));
cout << res << "\n";
}
}
return 0;
}


emanual20
10天前

# Sugar Water 2

### 题意

($n, m \le 5e4, 1 \le K \le N*M, 1 \le a_i, b_i, c_i, d_i \le 1e5$)

### 题解

/**
* @file template.cpp
* @author Emanual20(Emanual20@foxmail.com)
* @brief For Codeforces, Atcoder or some other OJs else
* @version 0.1
* @date 2023-3-19
*
*
*/
#pragma GCC optimize(2)
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const long double eps = 1e-12;
int n, m;
ll k;
struct item{
int s, w;
};
vector<item> va, vb;

bool check(long double ck){
long double portion = ck / (1 - ck);
ll tot = 0;
vector<long double> v;
for (int i = 0; i < m; i++){
long double res = vb[i].s - vb[i].w * portion;
v.push_back(res);
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++){
long double res = va[i].s - va[i].w * portion;
tot += v.end() - lower_bound(v.begin(), v.end(), -res);
}
// cout << ck << " " << tot << endl;
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);

cin >> n >> m >> k;
va = vector<item>(n, {0, 0}), vb = vector<item>(m, {0, 0});
for (int i = 0; i < n; i++){
cin >> va[i].s >> va[i].w;
}
for (int i = 0; i < m; i++){
cin >> vb[i].s >> vb[i].w;
}

long double l = 0, r = 1;
while(abs(l - r) > eps){
long double mid = (l + r) / 2;
if(check(mid)){
l = mid;
}
else
r = mid;
}
cout << fixed << setprecision(10) << l * 100 << endl;
return 0;
}


emanual20
11天前

## Question D Minimum Time to Repair Cars

### 题意

($n\le 1e5, ranks[i]\le 100, p \le 1e6$)

### 题解

typedef long long ll;
class Solution {
public:
vector<int> rk;
int goal;
bool check(ll rt){
ll tot = 0;
for(int i = 0; i < rk.size(); i++){
tot += floor(sqrt(rt * 1.0 / rk[i]));
}
}
long long repairCars(vector<int>& ranks, int cars) {
rk = ranks, goal = cars;
ll l = 1, r = 1e14;
while(l < r){
ll mid = (l + r) >> 1;
if(check(mid)){
r = mid;
}
else{
l = mid + 1;
}
}
return l;
}
};


## Question C Find Score of an Array After Marking All Elements

### 题意

• 在nums数组中选择一个最小的未被标记的元素nums[i]，如果有相同的元素，选择最小的那个下标。
• score += nums[i]
• 标记选中的元素和其相邻的元素nums[i-1]和nums[i+1]
• 重复上述操作直至所有元素被标记

($n \le 1e5, a[i] \le 1e6$)

### 题解

typedef long long ll;
class Solution {
public:
long long findScore(vector<int>& nums) {
ll ret = 0;
int n = nums.size();
vector<int> flag(n, 1);
map<int, set<int>> mp;
for(int i = 0; i < n; i++){
mp[nums[i]].insert(i);
}
while(mp.size() > 0){
auto it = mp.begin();
int itk = it->first;
set<int>& itv = it->second;
auto itvf = itv.begin();

ret += itk;

int lidx = (*itvf) - 1, idx = (*itvf), ridx = (*itvf) + 1;
if(lidx >= 0 && lidx < n && flag[lidx]){
flag[lidx] = 0, mp[nums[lidx]].erase(lidx);
if(mp[nums[lidx]].size() == 0) mp.erase(nums[lidx]);
}
if(ridx >= 0 && ridx < n && flag[ridx]){
flag[ridx] = 0, mp[nums[ridx]].erase(ridx);
if(mp[nums[ridx]].size() == 0) mp.erase(nums[ridx]);
}

flag[idx] = 0, mp[nums[idx]].erase(idx);
if(mp[nums[idx]].size() == 0) mp.erase(nums[idx]);
}
return ret;
}
};


## Question B Maximize Greatness of an Array

### 题意

($n\le 1e5, a[i] \le 1e9$)

### 题解

class Solution {
public:
int maximizeGreatness(vector<int>& a) {
int n = a.size();
sort(a.begin(), a.end());
int ret = 0, idy = 0;
for(int i = 0; i < n && idy < n; i++){
while(idy < n){
if(a[idy] <= a[i])
idy++;
else{
ret++, idy++;
break;
}
}
}
return ret;
}
};


## Question A Distribute Money to Maximum Children

### 题意

You are given an integer money denoting the amount of money (in dollars) that you have and another integer children denoting the number of children that you must distribute the money to.
You have to distribute the money according to the following rules:
All money must be distributed.
Everyone must receive at least 1 dollar.
Return the maximum number of children who may receive exactly 8 dollars if you distribute the money according to the aforementioned rules. If there is no way to distribute the money, return -1.

### 题解

class Solution {
public:
int distMoney(int money, int children) {
if(money < children || (money == 4 && children == 1)) return -1;
if(money == children * 8) return children;
if(money > children * 8) return children - 1;
money -= children;
return (money / 7) - (money % 7 == 3 && children - money / 7 == 1 ? 1 : 0);
}
};


emanual20
18天前

### 题面

($1\le A, M \le 1e9, 1\le X \le 1e12$)

### 题解

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

vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
res[i][j] += a[i][k] * b[k][j];
res[i][j] %= mod;
}
}
}
return res;
}

vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++) res[i][i] = 1;
while (b) {
if (b & 1) res = mat_mul(res, a, mod);
a = mat_mul(a, a, mod);
b >>= 1;
}
return res;
}

int main() {
ll a, x, m;
cin >> a >> x >> m;
vector<vector<ll>> f = { {a,1},{0,1} };
vector<vector<ll>> g = mat_pow(f, x, m);
cout << g[0][1] << endl;
return 0;
}


emanual20
19天前

## Question D Count Number of Possible Root Nodes

### 题意

($n\le 1e5, m\le 1e5, k \le m$)

### 题解

- 存在(u, v)，就-1，因为即将变成错的；
- 存在(v, u)，就+1，因为即将变成对的。

const int maxn = 1e5 + 10;
class Solution {
public:
int n;
vector<int> edges[maxn];
set<pair<int, int>> st;
int res = 0;
map<int, int> mp_ans;

void dfs1(int now, int fm){
res += st.count({fm, now}) > 0;
for(auto &nto : edges[now]){
if(nto != fm){
dfs1(nto, now);
}
}
}

void dfs2(int now, int fm){
if(mp_ans.find(now) == mp_ans.end())
mp_ans[now] = res;
for(auto &nto : edges[now]){
if(nto != fm){
res += st.count({nto, now}) > 0, res -= st.count({now, nto}) > 0;
dfs2(nto, now);
res -= st.count({nto, now}) > 0, res += st.count({now, nto}) > 0;
}
}
}

int rootCount(vector<vector<int>>& e, vector<vector<int>>& g, int k) {
n = e.size() + 1;
for(auto &it : e)
edges[it[0]].push_back(it[1]), edges[it[1]].push_back(it[0]);
for(auto &it : g)
st.insert({it[0], it[1]});
int root = 0; res = 0;
dfs1(root, -1);
dfs2(root, -1);

int ret = 0;
for(int i = 0; i < n; i++){
// cout << i << " :" << mp_ans[i] << endl;
ret += mp_ans[i] >= k;
}
return ret;
}
};


## Question C Count Ways to Group Overlapping Ranges

### 题意

• 每个range元素属于唯一的部分
• 任意两个重叠的区间属于相同的部分

### 题解

typedef long long ll;
const ll MOD = 1e9 + 7;

struct line{
int x, y;
};

bool comp(line l1, line l2){
if(l1.x != l2.x) return l1.x < l2.x;
else return l1.y > l2.y;
}

class Solution {
public:
int countWays(vector<vector<int>>& ranges) {
int n = ranges.size();
ll ret = 1;
vector<line> v;
for(auto &it : ranges) v.push_back({it[0], it[1]});
sort(v.begin(), v.end(), comp);
ll tot = 0, res = -1;
for(int i = 0; i < n; i++){
ll nx = v[i].x, ny = v[i].y;
if(nx > res){
tot += 1, res = max(res, ny);
}
else{
res = max(res, ny);
}
}

for(int i = 0; i < tot; i++){
ret *= 2, ret %= MOD;
}
return ret;
}
};


## Question B Count Total Number of Colored Cells

### 题解

typedef long long ll;
class Solution {
public:
long long coloredCells(int n) {
ll ret = 2ll * n * (n - 1) + 1;
return ret;
}
};


## Question A Split With Minimum Sum

### 题解

class Solution {
public:
int splitNum(int num) {
int nums1 = 0, nums2 = 0;
string s = to_string(num);
sort(s.begin(), s.end());
int n = s.length(), res[2] = {0, 0}, flag = 0;
for(int i = 0; i < n; i++){
res[flag] *= 10, res[flag] += (s[i] - '0'), flag = !flag;
}
return res[0] + res[1];
}
};


emanual20
1个月前

## Question D Minimum Time to Visit a Cell In a Grid

### 题解

• $t_v \ge t_u + 1$
• $t_v \ge grid[v.x][v.y]$

### 代码

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
class Solution {
public:
int minimumTime(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
priority_queue<piii> q;
int dis[n][m];
memset(dis, -1, sizeof(dis));
q.push(piii(0, pii(0, 0)));
while (!q.empty()) {
auto p = q.top(); q.pop();
int i = p.second.first, j = p.second.second;
if (dis[i][j] >= 0) continue;
dis[i][j] = -p.first;
for (int k = 0; k < 4; k++) {
int nx = i + dir[k][0], ny = j + dir[k][1];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || dis[nx][ny] >= 0) continue;
int v = (dis[i][j] + 1 >= grid[nx][ny] ? dis[i][j] + 1 : grid[nx][ny] + (grid[nx][ny] % 2 != (nx + ny) % 2));
q.push(piii(-v, pii(nx, ny)));
}
}
return dis[n - 1][m - 1];
}
};


## Question C Find the Maximum Number of Marked Indices

### 题解

class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int l = 0, r = (n + 1) / 2;
while(r < n){
if(nums[l] * 2 <= nums[r]) l += 1;
r += 1;
}
return l * 2;
}
};


## Question B Find the Divisibility Array of a String

### 涉及知识点

typedef long long ll;
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
int n = word.length();
vector<int> ret(n, 0);
ll res = 0;
for(int i = 0; i < n; i++){
res *= 10;
res += (word[i] - '0');
ret[i] = (res % m == 0);
res %= m;
}
return ret;
}
};


## Question A Left and Right Sum Differences

### 涉及知识点

class Solution {
public:
vector<int> leftRigthDifference(vector<int>& nums) {
int n = nums.size();
vector<int> lsum(n + 1, 0), rsum(n + 1, 0);
for(int i = 1; i <= n; i++){
lsum[i] = lsum[i - 1] + nums[i - 1];
}
for(int i = n - 1; i >= 0; i--){
rsum[i] = rsum[i + 1] + nums[i];
}
vector<int> ret(n, 0);
for(int i = 0; i < n; i++){
ret[i] = abs(lsum[i] - rsum[i + 1]);
}
return ret;
}
};


emanual20
1个月前

## Question C Count the Number of Square-Free Subsets

### 题意

($n\le1000, nums[i]\le30$)

### 题解

“复杂度”应该是需要最多计算(10*2^8)次

// 枚举合数的选取情况，对于每种枚举方式看还有哪些质数可以用
typedef long long ll;
const ll MOD = 1e9 + 7;
struct item{
ll prime, tot;
};
class Solution {
public:
int flag[31];
ll res = 0;
map<int, int> mp;
map<int, vector<item>> facmp;
set<map<int, int>> smp;

vector<item> Prime_Factorization(int x){
vector<item> ret;
for (int i = 2; i <= x / i; i++){
if(x % i == 0){
int tot = 0;
while(x % i == 0){
x /= i, tot++;
}
ret.push_back({i, tot});
}
}
if(x > 1) ret.push_back({x, 1});
return ret;
}
bool check(map<int, int> nusage, map<int, int> now){
bool ret = true;
for(auto &it : nusage)
ret = ret && (it.second <= min(1, mp[it.first]));
for(auto &it : now)
ret = ret && (it.second <= 1);
return ret;
}
void dfs(map<int, int> usage, map<int, int> st){
if(!check(usage, st) || smp.find(usage) != smp.end()){
return;
}
else{
ll tmp = 1;
for(auto &it : st){
if(it.second == 0 && mp[it.first] >= 1)
tmp *= (1 + mp[it.first]);
}
for(auto &it : usage){
if(it.second >= 1)
tmp *= mp[it.first];
}
res = (res + tmp) % MOD;
smp.insert(usage);
}
for(auto &it : usage){
if(mp[it.first] > 0 && it.second == 0){
usage[it.first] = 1;
auto nfac = facmp[it.first];
for(auto &it : nfac)
st[it.prime] += it.tot;

dfs(usage, st);

for(auto &it : nfac)
st[it.prime] -= it.tot;
usage[it.first] = 0;
}
}
}
int squareFreeSubsets(vector<int>& nums) {
for(auto &it : nums) mp[it] += 1;
for(auto &it : mp) facmp[it.first] = Prime_Factorization(it.first);
memset(flag, 0, sizeof(flag));
flag[2] = flag[3] = flag[5] = flag[7] = flag[11] = flag[13] = flag[17] = flag[19] = flag[23] = flag[29] = 1;
map<int, int> nusage;
nusage[6] = nusage[10] = nusage[14] = nusage[15] = nusage[21] = nusage[22] = nusage[26] = nusage[30] = 0;
map<int, int> nst;
for(int i = 1; i <= 30; i++) if(flag[i]) nst[i] = 0;
dfs(nusage, nst);
for(int i = 0; i < mp[1]; i++)
res *= 2, res %= MOD;
return (res - 1 + MOD) % MOD;
}
};


## Question B Minimum Operations to Reduce an Integer to 0

### 题意

($n\le1e5$)

### 题解

const int maxn = 1e5 + 10;
class Solution {
public:
int dp[maxn * 2];
int minOperations(int n) {
memset(dp, 0x3f, sizeof(dp));
queue<pair<int, int>> q;
dp[0] = 0, q.push({0, 0});
while(!q.empty()){
auto now = q.front();
for(int i = 0; i < 17; i++){
auto nvalue = now.first + (1 << i);
if(nvalue <= 2e5 && dp[nvalue] > now.second + 1){
dp[nvalue] = now.second + 1, q.push({nvalue, now.second + 1});
}
nvalue = now.first - (1 << i);
if(nvalue >= 0 && nvalue <= 2e5 && dp[nvalue] > now.second + 1){
dp[nvalue] = now.second + 1, q.push({nvalue, now.second + 1});
}
}
q.pop();
}
return dp[n];
}
};


## Question A Merge Two 2D Arrays by Summing Values

### 代码

class Solution {
public:
vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
map<int, int> mp;
for(auto &it : nums1){
mp[it[0]] += it[1];
}
for(auto &it : nums2){
mp[it[0]] += it[1];
}
vector<vector<int>> ret;
for(auto &it : mp){
ret.push_back(vector<int>{it.first, it.second});
}
return ret;
}
};


emanual20
1个月前

## Question D Handling Sum Queries After Update

### 题意

• “1 l r”，表示对nums1[l:r]上的0变为1，1变为0；
• “2 p 0”，表示对nums2[1:n]上的所有nums2[i] += p * nums1[i]
• “3 0 0”, 表示求$\sum_{i=1}^{n} nums2[i]$

($n \le 1e5, q \le 1e5, p \le 1e6$)

### 题解

typedef long long ll;
#define ls(k) ((k)<<1)
#define rs(k) (ls(k)^1)
#define mid ((l+r)>>1)

const int maxn = 1e5 + 10;

struct Node {
int len,sum;
int l[2],r[2],res[2];
int same,flip;
Node():same(-1),flip(0) {}
void turn(int k) {
l[k]=r[k]=res[k]=len,
l[k^1]=r[k^1]=res[k^1]=0;
sum=!k?0:len;
same=k, flip=0;
}
void rev() {
swap(l[0],l[1]), swap(r[0],r[1]), swap(res[0],res[1]);
sum=len-sum;
flip^=1;
}
};

class Solution {
public:
int n;
int a[maxn];
Node node[maxn*4];

void pushdown(int k) {
Node &ls=node[ls(k)], &rs=node[rs(k)];
int &same=node[k].same, &flip=node[k].flip;
if(same!=-1) {
ls.turn(same), rs.turn(same);
same=-1;
}
if(flip==1) {
ls.rev(), rs.rev();
flip=0;
}
}

Node maintain(const Node &ls,const Node &rs) {
Node R;
R.len=ls.len+rs.len, R.sum=ls.sum+rs.sum;
for(int i=0;i<2;i++) {
R.l[i]=ls.l[i], R.r[i]=rs.r[i];
if(ls.l[i]==ls.len) R.l[i]=ls.len+rs.l[i];
if(rs.r[i]==rs.len) R.r[i]=rs.len+ls.r[i];
R.res[i]=max(max(R.l[i],R.r[i]),ls.r[i]+rs.l[i]);
R.res[i]=max(R.res[i],max(ls.res[i],rs.res[i]));
}
R.same=-1, R.flip=0;
return R;
}

void build(int k,int l,int r) {
node[k].len=r-l+1;
if(l==r) {
int x=a[l];
node[k].l[x]=node[k].r[x]=node[k].res[x]=1;
node[k].sum=x;
return;
}
build(ls(k),l,mid);
build(rs(k),mid+1,r);
node[k]=maintain(node[ls(k)],node[rs(k)]);
return;
}

void flip(int k,int l,int r,int ql,int qr) {
if(l!=r) pushdown(k);
if(ql<=l && r<=qr) {
node[k].rev();
return;
}
if(ql<=mid) flip(ls(k),l,mid,ql,qr);
if(qr> mid) flip(rs(k),mid+1,r,ql,qr);
node[k]=maintain(node[ls(k)],node[rs(k)]);
return;
}

void flip(int l,int r) {
flip(1,1,n,l,r);
}

Node query(int k,int l,int r,int ql,int qr) {
if(l!=r) pushdown(k);
if(ql<=l && r<=qr) return node[k];
if(qr<=mid) return query(ls(k),l,mid,ql,qr);
else if(ql>mid) return query(rs(k),mid+1,r,ql,qr);
else return maintain(query(ls(k),l,mid,ql,qr),query(rs(k),mid+1,r,ql,qr));
}

int query_sum(int l,int r) {
Node ans=query(1,1,n,l,r);
return ans.sum;
}

public:
vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
vector<ll> ret;
ll res = 0;
n = nums1.size();
for(int i = 0; i < n; i++){
a[i + 1] = nums1[i];
}
build(1, 1, n);
for(auto &it : nums2){
res += it;
}
for(auto &q : queries) {
int op = q[0], x = q[1], y = q[2];
if(op == 1)
x += 1, y += 1, flip(x, y);
else if(op == 2){
res += query_sum(1, n) * 1ll * x;
}
else if(op == 3){
ret.push_back(res);
}
}
return ret;
}
};


## Question C Minimum Impossible OR

### 题解

class Solution {
public:
int minImpossibleOR(vector<int>& nums) {
int tt = 1;
set<int> st;
for(auto &it : nums) st.insert(it);
for(int i = 1; i <= 31; i++){
if(st.count(tt) == 0){
return tt;
}
tt *= 2;
}
return tt;
}
};


## Question B Minimum Score by Changing Two Elements

### 题解

class Solution {
public:
int minimizeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int cand1 = abs(nums[n - 1] - nums[2]), cand2 = abs(nums[n - 2] - nums[1]), cand3 = abs(nums[n - 3] - nums[0]);
return min(cand1, min(cand2, cand3));
}
};


## Question A Maximum Difference by Remapping a Digit

### 代码

class Solution {
public:
int minMaxDifference(int num) {
string res = to_string(num);
int mini = num, maxi = num;
for(int dfm = '0'; dfm <= '9'; dfm++){
for(int dto = '0'; dto <= '9'; dto++){
string temp = res;
int x = 0;
for(auto &it : temp){
if(it == dfm)
it = dto;
}
for(int i = 0; i < temp.length(); i++){
x *= 10, x += (temp[i] - '0');
}
mini = min(mini, x), maxi = max(maxi, x);
}
}
return maxi - mini;
}
};