A. Distance and Axis
如果(B)在(O)左边，那么只能是定值(OA)
如果(B)在(OA)中间，那么必然小于等于(OA)且奇偶性和(OA)相同
(B)在(A)右边的情况显然不如(B)和(A)重合
所以分(kle n)和(k>n)分类讨论即可
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 2e5+7;
void solve(){
int n, k;
sci(n); sci(k);
if(k<=n){
if((k&1)==(n&1)) cout << 0 << endl;
else cout << 1 << endl;
}else cout << k - n << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
int tt; for(sci(tt); tt--; solve());
return 0;
}
B. Ternary Sequence
显然要拿(A)的(2)和(B)的(1)组合，尽量得到大的值，然后拿(A)的(0)和(2)去和(B)的(2)组合，尽量避免出现负数，如果(A)还有(1)，(B)还有(2)，那么没办法只能组合了，剩下的数怎么组合贡献都是(0)
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 2e5+7;
void solve(){
int x, y, z, a, b, c;
sci(x); sci(y); sci(z); sci(a); sci(b); sci(c);
int ret = min(z,b) * 2;
z -= ret / 2; b -= ret / 2;
int d = min(x,c);
x -= d; c -= d;
d = min(z,c);
z -= d; c -= d;
ret -= c * 2;
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
int tt; for(sci(tt); tt--; solve());
return 0;
}
C. Mere Array
考虑三个数(a,b,c)，(a)是数列中最小的数，$b ≡ 0 mod a (且)c≡0mod a(，那么通过)a(可以使得)a,b,c$任意排序
所以考虑把原序列排序，找出那些和原序列值不同的位置，如果这些位置上的值都能被最小值整除，那么就可以得到排序后的序列
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 2e5+7;
void solve(){
int n; sci(n);
vi A(n); for(int &x : A) sci(x);
int x = *min_element(all(A));
vi B(A);
sort(all(B));
for(int i = 0; i < n; i++){
if(A[i]==B[i]) continue;
if(A[i]%x!=0){
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
int tt; for(sci(tt); tt--; solve());
return 0;
}
D. Maximum Distributed Tree
考虑计算每条边的贡献，可以发现每条边对(sz_vcdot (n-sz_v))个点对距离有贡献，其中(v)为边对应的子节点
考虑把边按贡献数排序，因子也排序，贡献大的赋的值也要尽量大，如果(m<=n-1)的话就给前(m)大贡献的边赋值对应的因子，否则给后(n-2)条边赋值对应小的因子，然后剩下的乘积赋给贡献最大的边
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 2e5+7;
const int MOD = 1e9+7;
vi G[MAXN];
int n, m, sz[MAXN];
vl cont;
void dfs(int u, int par){
sz[u] = 1;
for(int v : G[u]){
if(v==par) continue;
dfs(v,u);
sz[u] += sz[v];
cont << (1ll * sz[v] * (n - sz[v]));
}
}
void solve(){
sci(n);
for(int i = 1; i <= n; i++) G[i].clear();
for(int i = 1; i < n; i++){
int u, v;
sci(u); sci(v);
G[u] << v; G[v] << u;
}
sci(m);
vi f(m);
for(int &x : f) sci(x);
sort(all(f),greater<int>());
cont.clear();
dfs(1,0);
sort(all(cont),greater<LL>());
LL ret = 0;
if(m<=n-1){
for(int i = 0; i < m; i++) ret = (ret + cont[i] % MOD * f[i]) % MOD;
for(int i = m; i < n - 1; i++) ret = (ret + cont[i]) % MOD;
}else{
LL prod = 1;
for(int i = 0; i < m - n + 2; i++) prod = prod * f[i] % MOD;
for(int i = m - n + 2; i < m; i++) ret = (ret + cont[i-m+n-2+1] % MOD * f[i]) % MOD;
ret = (ret + cont[0] % MOD * prod) % MOD;
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
int tt; for(sci(tt); tt--; solve());
return 0;
}
E. Divide Square
考虑固定横向的边，初始正方形的块数是(1)，竖着的边和横着的边每有一个交点，都会多分出来一块
所以问题转化为计算交点数量，这个用扫描线就完事了
注意联通正方形两端的边会多分割出一块来
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 1e6+7;
const int lim = 1000000;
struct SegmentTree{
int sum[MAXN<<2], l[MAXN<<2], r[MAXN<<2];
#define ls(rt) rt << 1
#define rs(rt) rt << 1 | 1
void build(int L, int R, int rt = 1){
l[rt] = L, r[rt] = R;
if(L + 1 == R) return;
int mid = (L + R) >> 1;
build(L,mid,ls(rt)); build(mid,R,rs(rt));
}
void modify(int pos, int x, int rt = 1){
sum[rt] += x;
if(l[rt] + 1 == r[rt]) return;
int mid = (l[rt] + r[rt]) >> 1;
if(pos<mid) modify(pos,x,ls(rt));
else modify(pos,x,rs(rt));
}
int qsum(int L, int R, int rt = 1){
if(L>=r[rt] or l[rt]>=R) return 0;
if(L<=l[rt] and r[rt]<=R) return sum[rt];
return qsum(L,R,ls(rt)) + qsum(L,R,rs(rt));
}
}ST;
int n, m;
pii line[MAXN];
vector<pii> vec[MAXN];
void solve(){
sci(n); sci(m);
for(int i = 1; i <= n; i++){
int y; sci(y);
sci(line[y].first), sci(line[y].second);
}
ST.build(0,lim+1);
ST.modify(0,1); ST.modify(lim,1);
LL ret = 1;
for(int i = 1; i <= m; i++){
int x; sci(x);
int a, b; sci(a); sci(b);
if(b-a==lim) ret++;
if(!a){
ST.modify(x,1);
vec[b] << pii(x,-1);
}else vec[a] << pii(x,1);
}
for(int i = 1; i <= lim; i++){
for(auto &p : vec[i]) if(p.second==1) ST.modify(p.first,p.second);
if(line[i].first + line[i].second) ret += ST.qsum(line[i].first,line[i].second+1) - 1;
for(auto &p : vec[i]) if(p.second==-1) ST.modify(p.first,p.second);
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
F. Reverse and Swap
建一棵线段树，显然线段树是满二叉树
考虑(reverse(k))操作，我们可以先打懒标记，然后不断下传，直到遇到线段树上某个节点(rt)且(r_{rt}-l_{rt}=2^k)的时候，我们可以把(reverse(k))这个操作变为交换两个儿子，然后分别再对两个儿子进行(reverse(k-1))
(swap(k))这个操作也可以打懒标记，然后遇到节点(rt)满足(r_{rt}-l_{rt}=2^{k+1})的时候，我们交换两个儿子即可
可以发现两个(reverse(k))可以抵消，两个(swap(k))也可以抵消，所以考虑用二进制来存懒标记，然后用异或来打标记
然后合在一起考虑的时候就分类讨论一下即可
-
如果只有(reverse(k))，直接交换两个儿子，然后分别加上(reverse(k-1))的标记
-
如果只有(swap(k-1))标记，交换两个儿子就好了
-
都有的情况，那就不用交换儿子，直接给两个儿子分别加上(reverse(k-1))标记即可
注意要把标记全部下传然后清空
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define pll pair<LL,LL>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x) cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
template <typename T> void operator << (vector<T> &__container, T x){ __container.push_back(x); }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; }
const int MAXN = 1e6+7;
int n, q, A[MAXN];
struct SegmentTree{
int ls[MAXN<<2], rs[MAXN<<2], tot, root;
LL sum[MAXN];
int swp[MAXN<<2], rev[MAXN<<2];
#define pushup(rt) sum[rt] = sum[ls[rt]] + sum[rs[rt]]
void build(int L, int R, int &rt){
rt = ++tot;
if(L + 1 == R){
sum[rt] = A[L];
return;
}
int mid = (L + R) >> 1;
build(L,mid,ls[rt]); build(mid,R,rs[rt]);
pushup(rt);
}
void pushdown(int rt, int l, int r){
int len = r - l;
int bit = __builtin_ctz(len);
if(rev[rt]>>bit&1){
if(swp[rt]>>(bit-1)&1){
rev[rt] ^= (1 << bit) ^ (1 << (bit - 1));
swp[rt] ^= (1 << (bit - 1));
}else{
rev[rt] ^= (1 << bit) ^ (1 << (bit - 1));
std::swap(ls[rt],rs[rt]);
}
}else if(swp[rt]>>(bit-1)&1){
swp[rt] ^= (1 << (bit - 1));
std::swap(ls[rt],rs[rt]);
}
rev[ls[rt]] ^= rev[rt]; rev[rs[rt]] ^= rev[rt];
swp[ls[rt]] ^= swp[rt]; swp[rs[rt]] ^= swp[rt];
rev[rt] = swp[rt] = 0;
}
void swap(int k){ swp[root] ^= (1 << k); }
void reverse(int k){ rev[root] ^= (1 << k); }
void modify(int pos, int x, int l, int r, int rt){
if(l + 1 == r){
sum[rt] = x;
return;
}
pushdown(rt,l,r);
int mid = (l + r) >> 1;
if(pos < mid) modify(pos,x,l,mid,ls[rt]);
else modify(pos,x,mid,r,rs[rt]);
pushup(rt);
}
LL qsum(int L, int R, int l, int r, int rt){
if(l>=R or L>=r) return 0;
if(L<=l and r<=R) return sum[rt];
pushdown(rt,l,r);
int mid = (l + r) >> 1;
return qsum(L,R,l,mid,ls[rt]) + qsum(L,R,mid,r,rs[rt]);
}
}ST;
void solve(){
sci(n); sci(q);
for(int i = 0; i < (1 << n); i++) sci(A[i]);
ST.build(0,1<<n,ST.root);
while(q--){
int type; sci(type);
if(type==1){
int x, k; sci(x), sci(k);
ST.modify(x-1,k,0,1<<n,ST.root);
}else if(type==2){
int k; sci(k);
ST.reverse(k);
}else if(type==3){
int k; sci(k);
ST.swap(k);
}else{
int l, r; sci(l); sci(r);
printf("%I64d
",ST.qsum(l-1,r,0,1<<n,ST.root));
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}