D. Almost Acyclic Graph
首先想到枚举所有的边，然后判断删掉之后是否还有环，这样的话复杂度会到(O(m^2))，发现(n)很小，那么最大的环大小不会超过(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 endl "
"
#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 scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#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> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 5e2+7;
vi G[MAXN];
bool vis[MAXN], instk[MAXN];
stack<int> stk;
vector<int> vec;
void dfs(int u){
vis[u] = true;
stk.push(u);
instk[u] = true;
for(int v : G[u]){
if(!vis[v]) dfs(v);
else if(instk[v]){
do{
vec << stk.top();
stk.pop();
}while(vec.back()!=v);
reverse(all(vec));
}
if(!vec.empty()) return;
}
instk[u] = false;
stk.pop();
}
void solve(){
int n, m;
sci(n); sci(m);
for(int i = 1; i <= m; i++){
int u, v; sci(u); sci(v);
G[u] << v;
}
for(int i = 1; i <= n; i++) if(!vis[i]){
dfs(i);
if(!vec.empty()) break;
}
if(vec.empty()){
cout << "YES" << endl;
return;
}
bool ok = false;
auto test = [&](int a, int b){
vi deg(n+1,0);
for(int i = 1; i <= n; i++) for(int v : G[i]){
if(i==a and v==b) continue;
deg[v]++;
}
int used = 0;
queue<int> que;
for(int i = 1; i <= n; i++) if(!deg[i]) que.push(i);
while(!que.empty()){
int u = que.front();
que.pop(), used++;
for(int v : G[u]){
if(u==a and v==b) continue;
if(!--deg[v]) que.push(v);
}
}
return used==n;
};
for(int i = 0; i < vec.size() - 1; i++){
if(test(vec[i],vec[i+1])){
ok = true;
break;
}
}
if(test(vec.back(),vec.front())) ok = true;
cout << (ok ? "YES" : "NO") << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
E. Physical Education Lessons
那么对于这种区间范围很大的数据结构题，一般离散化之后用线段树来做，或者动态开点线段树
这里考虑离散化之后用线段树来做，注意把每个要离散化点的右端点也加进去，保证这个点在线段树上的区间范围是(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 endl "
"
#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 scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#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> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 1.2e6+7;
int n, q;
vector<int> vec;
struct STA{
int l, r, k;
}sta[MAXN];
struct SegmentTree{
int l[MAXN<<2], r[MAXN<<2], sum[MAXN<<2], lazy[MAXN<<2];
#define ls(rt) rt << 1
#define rs(rt) rt << 1 | 1
#define pushup(rt) sum[rt] = sum[ls(rt)] + sum[rs(rt)]
void build(int L, int R, int rt = 1){
l[rt] = L; r[rt] = R;
lazy[rt] = -1;
if(L + 1 == R){
sum[rt] = vec[r[rt]] - vec[l[rt]];
return;
}
int mid = (L + R) >> 1;
build(L,mid,ls(rt)); build(mid,R,rs(rt));
pushup(rt);
}
void pushdown(int rt){
if(lazy[rt]==-1) return;
lazy[ls(rt)] = lazy[rs(rt)] = lazy[rt];
if(lazy[rt]==1){
sum[ls(rt)] = vec[r[ls(rt)]] - vec[l[ls(rt)]];
sum[rs(rt)] = vec[r[rs(rt)]] - vec[l[rs(rt)]];
}else sum[ls(rt)] = sum[rs(rt)] = 0;
lazy[rt] = -1;
return;
}
void modify(int L, int R, int x, int rt = 1){
if(L>=r[rt] or l[rt]>=R) return;
if(L<=l[rt] and r[rt]<=R){
lazy[rt] = x;
if(x==1) sum[rt] = vec[r[rt]] - vec[l[rt]];
else sum[rt] = 0;
return;
}
pushdown(rt);
modify(L,R,x,ls(rt)); modify(L,R,x,rs(rt));
pushup(rt);
}
int query(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];
pushdown(rt);
return query(L,R,ls(rt)) + query(L,R,rs(rt));
}
}ST;
void solve(){
sci(n); sci(q);
for(int i = 1; i <= q; i++){
sci(sta[i].l); sci(sta[i].r); sci(sta[i].k);
vec << sta[i].l << sta[i].r;
if(sta[i].l+1<=n) vec << sta[i].l+1;
if(sta[i].r+1<=n) vec << sta[i].r+1;
}
sort(all(vec)); vec.erase(unique(all(vec)),vec.end());
vec.push_back(vec.back()+1);
for(int i = 1; i <= q; i++){
sta[i].l = lower_bound(all(vec),sta[i].l) - vec.begin();
sta[i].r = lower_bound(all(vec),sta[i].r) - vec.begin();
}
int ret = n;
ST.build(0,vec.size()-1);
for(int i = 1; i <= q; i++){
int k = sta[i].k, l = sta[i].l, r = sta[i].r;
ret -= ST.query(l,r+1);
ST.modify(l,r+1,k-1);
if(k==2) ret += vec[r] - vec[l] + 1;
cout << ret << endl;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
F. Imbalance Value of a Tree
首先，可以把问题转化为任意两点间最大值的和减去最小值的和
以最大值为例，最小值类似
考虑类似点分治的思想，每次找到所有点中的最大值，然后计算这个点的贡献就是经过这个点的所有路径的数量乘上点权，然后把这个点删掉之后变成几个子树，分治解决，但是每次找到的点不是树的重心，所以分治复杂度最坏会到达(O(n^2))
考虑反着来做，每次找到当前最小的点，然后把连着的所有比他小的点都连起来，然后算当前连通块的贡献，可以用并查集来做，复杂度为(O(nlog n))
对于某个连通块，假设当前的最大值点为(u)，那么路径的总数应该等于任意两个子树的大小的乘积加上总的大小，前者可以用前缀和来优化计算
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#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 scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#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> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 1e6+7;
int n, app[MAXN], root[MAXN], sz[MAXN];
pair<pii,int> w[MAXN], cp[MAXN];
vi G[MAXN];
int findx(int x){ return x==root[x]?x:root[x]=findx(root[x]); }
void solve(){
sci(n);
for(int i = 1; i <= n; i++){
sci(w[i].first.first);
w[i].first.second = ++app[w[i].first.first];
w[i].second = i;
cp[i] = w[i];
}
for(int i = 1; i < n; i++){
int u, v;
sci(u); sci(v);
G[u] << v; G[v] << u;
}
sort(cp+1,cp+1+n);
LL ret = 0;
for(int i = 1; i <= n; i++) sz[i] = 1, root[i] = i;
for(int i = 1; i <= n; i++){
vi vec, sum;
int u = cp[i].second;
for(int v : G[u]){
if(w[v].first < w[u].first){
vec << sz[findx(v)];
sz[findx(u)] += sz[findx(v)];
root[findx(v)] = findx(u);
}
}
partial_sum(all(vec),back_inserter(sum));
LL tot = 0;
for(int j = 1; j < vec.size(); j++) tot += 1ll * vec[j] * sum[j-1];
tot += sz[findx(u)];
ret += w[u].first.first * tot;
}
for(int i = 1; i <= n; i++) sz[i] = 1, root[i] = i;
for(int i = n; i >= 1; i--){
vi vec, sum;
int u = cp[i].second;
for(int v : G[u]){
if(w[v].first > w[u].first){
vec << sz[findx(v)];
sz[findx(u)] += sz[findx(v)];
root[findx(v)] = findx(u);
}
}
partial_sum(all(vec),back_inserter(sum));
LL tot = 0;
for(int j = 1; j < vec.size(); j++) tot += 1ll * vec[j] * sum[j-1];
tot += sz[findx(u)];
ret -= w[u].first.first * tot;
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}
G. Coprime Arrays
要计算(sum_{i=1}^k (sum_{a_1=1}^icdots sum_{a_n=1}^i[operatorname {gcd}(a_1cdots a_n)=1])oplus i)
考虑单独计算(g(i) = sum_{a_1=1}^icdots sum_{a_n=1}^i[operatorname {gcd}(a_1cdots a_n)=1])
通过莫比乌斯反演可以得到：(g(i) = sum_{a_1=1}^icdots sum_{a_n=1}^i[operatorname {gcd}(a_1cdots a_n)=1] = sum_{j=1}^imu(j)cdot lfloor frac ij floor^n)
如果直接用整除分块来做的话，复杂度是(O(sum_{i=1}^ksqrt i) = O(frac 23 k^{frac 32}))
考虑相邻两个(g(i),g(i-1))可以发现只有满足(jmid i)的(lfloor frac ij floor)发生了变化，所以考虑计算(f(i) = g(i)-g(i-1))，所有数的因子数的复杂度为(O(klog k))，再预处理一下所有的幂，总复杂度为(O(k(log n + log k)))
view code
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define endl "
"
#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 scs(s) scanf("%s",s)
#define pii pair<int,int>
#define pll pair<LL,LL>
#ifndef ONLINE_JUDGE
#define cout cerr
#endif
#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> vector<T>& operator << (vector<T> &__container, T x){ __container.push_back(x); return __container; }
template <typename T> ostream& operator << (ostream &out, vector<T> &__container){ for(T _ : __container) out << _ << ' '; return out; }
const int MAXN = 2e6+7;
const int MOD = 1e9+7;
int mu[MAXN], prime[MAXN], pri_cnt, pw[MAXN];
int f[MAXN];
bool npm[MAXN];
LL ksm(LL a, LL b){
LL ret = 1;
while(b){
if(b&1) ret = ret * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ret;
}
void sieve(){
mu[1] = 1;
for(int i = 2; i < MAXN; i++){
if(!npm[i]) prime[++pri_cnt] = i, mu[i] = -1;
for(int j = 1; i * prime[j] < MAXN; j++){
npm[i*prime[j]] = true;
if(i%prime[j]==0){
mu[i*prime[j]] = 0;
break;
}
mu[i*prime[j]] = -mu[i];
}
}
}
void solve(){
sieve();
int n, k;
sci(n); sci(k);
for(int i = 1; i <= k; i++) pw[i] = ksm(i,n);
for(int i = 1; i <= k; i++) for(int j = i; j <= k; j += i) f[j] = (f[j] + mu[i] * (pw[j/i] - pw[j/i-1])) % MOD;
int ret = 0, cur = 0;
for(int i = 1; i <= k; i++){
cur = ((cur + f[i]) % MOD + MOD) % MOD;
ret = (ret + (cur ^ i)) % MOD;
}
cout << ret << endl;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("Local.in","r",stdin);
freopen("ans.out","w",stdout);
#endif
solve();
return 0;
}