P2680 [NOIP2015 提高组] 运输计划
题意为让最长的路径最短，所以要 二分答案。
考虑如何写
设当前验证的答案为
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 3e5 + 5, M = 3e5 + 5;
struct Edge {
int to, nxt, wei;
} Edge[M << 1];
struct trans {
int u, v, dis, lca;
bool operator<(const trans& a) const {
return dis < a.dis;
}
} trans[N << 1];
int head[N], belongTo[N], cnt, n, m;
void addEdge(int u, int v, int w) {
Edge[++cnt].to = v;
Edge[cnt].nxt = head[u];
Edge[cnt].wei = w;
head[u] = cnt;
}
int f[N][21], dep[N], dis[N];
void dfs1(int u, int fa, int depth, int d) {
f[u][0] = fa; dep[u] = depth + 1; dis[u] = d;
for(int i = 1; i <= 20; i++) f[u][i] = f[f[u][i - 1]][i - 1];
for(int i = head[u]; i; i = Edge[i].nxt) {
const int &v = Edge[i].to;
if(v == fa) continue;
belongTo[v] = Edge[i].wei;
dfs1(v, u, depth + 1, d + Edge[i].wei);
}
}
int lca(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
int dis = dep[x] - dep[y];
for(int i = 20; ~i; i--) if(dis & (1 << i)) x = f[x][i];
if(x == y) return x;
for(int i = 20; ~i; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
int d[N], a[N];
void dfs2(int u, int fa) {
a[u] = d[u];
for(int i = head[u]; i; i = Edge[i].nxt) {
const int v = Edge[i].to;
if(v == fa) continue;
dfs2(v, u);
a[u] += a[v];
}
}
int judge(int x) {
d(x);
if(trans[m].dis <= x) return true;
std::fill(d, d + N, 0);
int lst = m;
for(int j = m; j && trans[j].dis > x; j--) {
lst = j;
d[trans[j].u]++; d[trans[j].v]++; d[trans[j].lca] -= 2;
}
d(lst);
std::fill(a, a + N, 0);
dfs2(1, 0);
int mx = 0;
for(int i = 2; i <= n; i++) {
if(m - lst + 1 == a[i]) mx = max(belongTo[i], mx);
}
if(trans[m].dis - mx <= x) return true;
return false;
}
signed main() {
#ifdef LOCAL
file();
#endif
n = rd(), m = rd();
for(int i = 1; i < n; i++) {
int u = rd(), v = rd(), w = rd();
addEdge(u, v, w); addEdge(v, u, w);
}
int l = 0, r = 0x3f3f3f3f, ans = 0;
dfs1(1, 0, 1, 0);
for(int i = 1; i <= m; i++) {
int u = rd(), v = rd();
int lcav = lca(u, v);
trans[i].u = u;
trans[i].v = v;
trans[i].dis = dis[u] + dis[v] - 2 * dis[lcav];
trans[i].lca = lcav;
}
sort(trans + 1, trans + m + 1);
while(l <= r) {
int mid = (l + r) >> 1;
if(judge(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
cout << ans << endl;
return 0;
}P7273 ix35 的等差数列
由于值域较小，可以考虑枚举公差。
构造数列
注意可能这种循环的写法可能爆 long long。
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
int n, w;
const int N = 3e5 + 6;
int a[N], b[N];
unordered_map<int, int> maps;
int judge(int d) {
b[1] = 1;
maps.clear();
for(int i = 2; i <= n; i++) b[i] = b[i - 1] + d;
for(int i = 1; i <= n; i++) maps[a[i] - b[i]]++;
int res = 0;
for(unordered_map<int, int>::iterator it = maps.begin(); it != maps.end(); it++) {
if(it -> first + b[1] < 1) continue;
if(it -> first + b[n] > w) continue;
res = max(res, it -> second);
}
return n - res;
}
signed main() {
#ifdef LOCAL
file();
#endif
n = rd(), w = rd();
for(int i = 1; i <= n; i++) a[i] = rd();
if(n == 1) return puts("0"), 0;
int ans = 0x3f3f3f3f;
for(int d = 0; d <= w; d++) {
if(1 + (n - 1) * d <= w) {
ans = min(ans, judge(d));
}
}
printf("%lld\n", ans);
return 0;
}
CF372C Watching Fireworks is Fun
单调队列优化 dp。
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1.5e5 + 5, M = 305;
struct Firework {
int a, b, t;
Firework() : a(0), b(0), t(0) { }
} fw[N];
int f[2][N];
deque<int> Q;
int myabs(int x) {
return x < 0 ? -x : x;
}
signed main() {
#ifdef LOCAL
file();
#endif
int n = rd(), m = rd(), d = rd();
for(int i = 1; i <= m; i++) {
fw[i].a = rd();
fw[i].b = rd();
fw[i].t = rd();
}
for(int i = 1; i <= m; ++i) {
Q.clear();
int ed = min(1 + (fw[i].t - fw[i - 1].t) * d, n);
for(int j = 1; j <= ed; j++) {
while(!Q.empty() && f[0][Q.back()] <= f[0][j]) Q.pop_back();
Q.push_back(j);
}
for(int j = 1; j <= n; j++) {
while(!Q.empty() && Q.front() < j - (fw[i].t - fw[i - 1].t) * d) Q.pop_front();
while (ed < min(j + (fw[i].t - fw[i - 1].t) * d, n)) {
++ed;
while(!Q.empty() && f[0][Q.back()] <= f[0][ed]) Q.pop_back();
Q.push_back(ed);
}
f[1][j] = fw[i].b - myabs(fw[i].a - j) + f[0][Q.front()];
}
for(int j = 1; j <= n; j++) {
f[0][j] = f[1][j];
}
std::fill(f[1] + 1, f[1] + n + 1, 0);
}
cout << *max_element(f[0] + 1, f[0] + n + 1) << endl;
return 0;
}
CF75C Modified GCD
一句话，两个数的公约数一定是他们最大公约数的约数。
另外
留一张图，约数质因子数量级表.jpg
图片上传锅了，等有时间搭个图床。
[PlaceHolder]
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
int gcd(int a, int b) {
return !b ? a : gcd(b, a % b);
}
vector<int> fac;
signed main() {
#ifdef LOCAL
file();
#endif
int x = rd(), y = rd();
int gcdv = gcd(x, y);
for(int i = 1; i * i <= gcdv; i++) {
if(gcdv % i == 0) {
fac.push_back(i);
if(gcdv / i != i) fac.push_back(gcdv / i);
}
}
sort(fac.begin(), fac.end());
int m = rd();
for(int i = 1; i <= m; i++) {
int a = rd(), b = rd();
auto p = upper_bound(fac.begin(), fac.end(), b);
if(p == fac.begin()) {
puts("-1");
continue;
}
--p;
if(a <= *p) {
printf("%d\n", *(p));
} else {
puts("-1");
}
}
return 0;
}P3609 [USACO17JAN]Hoof, Paper, Scissor G
比较激进的思路是不保留当前状态的出法（剪刀石头布），但这样会造成复杂度的退化
状态还是多保留一些信息好。。
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e5 + 5, M = 22;
#define Hoof 0
#define Scissors 1
#define Paper 2
const int table[3][3] = {
{0, 1, 0},
{0, 0, 1},
{1, 0, 0}
};
int f[N][M][3], g[N];
int judge(int a, int b) {
return table[a][b];
}
signed main() {
#ifdef LOCAL
file();
#endif
int n = rd(), k = rd();
for(int i = 1; i <= n; i++) {
char ch[5];
scanf("%s", ch + 1);
if(ch[1] == 'P') g[i] = Paper;
if(ch[1] == 'S') g[i] = Scissors;
if(ch[1] == 'H') g[i] = Hoof;
}
// for(int i = 1; i <= n; i++) cout << g[i] << endl;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k; j++) {
for(int u = 0; u < 3; u++) {
for(int b = 0; b < 3; b++) {
if(u == b) f[i][j][u] = max(f[i][j][u], f[i - 1][j][b] + judge(u, g[i]));
else if(j > 0) f[i][j][u] = max(f[i][j][u], f[i - 1][j - 1][b] + judge(u, g[i]));
}
}
}
}
int ans = 0;
for(int j = 0; j <= k; j++) {
for(int u = 0; u < 3; ++u) {
ans = max(ans, f[n][j][u]);
}
}
cout << ans << endl;
return 0;
}P3567 [POI2014]KUR-Couriers
可持久化数据结构系列。
主席树板子题。查询第
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, node[x].ls
#define rson mid + 1, r, node[x].rs
public :
static const int N = 5e5 + 5;
struct Node {
int ls, rs, sum;
} node[N * 40];
int root[N], cnt;
SegmentTree() : cnt(0) { }
int build(int l, int r) {
int x = ++cnt;
if(l == r) {
node[x].ls = node[x].rs = node[x].sum = 0;
return x;
}
MID;
node[x].ls = build(l, mid);
node[x].rs = build(mid + 1, r);
push_up(x);
return x;
}
int clone(int x) {
node[++cnt] = node[x];
return cnt;
}
void push_up(int x) {
node[x].sum = node[node[x].ls].sum + node[node[x].rs].sum;
}
void modify_add(int l, int r, int &x, int p, int v) {
x = clone(x);
if(l == r) {
node[x].sum += v;
return ;
}
MID;
if(p <= mid) modify_add(lson, p, v);
if(p > mid) modify_add(rson, p, v);
push_up(x);
}
int query(int a, int b, int n) {
int k = (b - a) / 2 + 1, ok = k;
int l = 1, r = n;
a = root[a], b = root[b];
while(l < r) {
MID;
int lsv = node[node[b].ls].sum - node[node[a].ls].sum;
if(lsv >= k) {
r = mid;
a = node[a].ls;
b = node[b].ls;
} else {
l = mid + 1;
k -= lsv;
a = node[a].rs;
b = node[b].rs;
}
}
return node[b].sum - node[a].sum >= ok ? l : 0;
}
} st;
signed main() {
#ifdef LOCAL
file();
#endif
int n = rd(), m = rd();
st.root[0] = st.build(1, n);
for(int i = 1; i <= n; i++) {
int v = rd();
st.root[i] = st.root[i - 1];
st.modify_add(1, n, st.root[i], v, 1);
}
// for(int i = 1; i <= n; i++) {
// cout << st.root[i] << " ";
// }
// cout << endl;
for(int i = 1; i <= m; ++i) {
int l = rd(), r = rd();
int res = st.query(l - 1, r, n);
printf("%d\n", res);
}
return 0;
}CF1474A - Puzzle From the Future
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
void solve() {
int n; cin >> n;
string a, b; cin >> b; a = b;
// cout << b << endl;
int bef = 0;
for(int i = 0; i < (int) b.size(); i++) {
if(b[i] == '1') {
if(bef == 2) a[i] = '0', bef = 1;
else if(bef == 1) a[i] = '1', bef = 2;
else if(bef == 0) a[i] = '1', bef = 2;
} else if(b[i] == '0') {
if(bef == 2) a[i] = '1', bef = 1;
else if(bef == 1) a[i] = '0', bef = 0;
else if(bef == 0) a[i] = '1', bef = 1;
}
}
cout << a << '\n';
}
signed main() {
#ifdef LOCAL
file();
#endif
int T; cin >> T;
while(T--) solve();
return 0;
}CF1474B - Different Divisors
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ "] on line " << __LINE__ << endl
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e5 + 6;
int isnt[N];
vector<int> Primes;
void solve() {
int d = rd();
int t = *(lower_bound(Primes.begin(), Primes.end(), 1 + d));
int x = *(lower_bound(Primes.begin(), Primes.end(), t + d));
printf("%d\n", t * x);
}
void init(int n) {
isnt[0] = isnt[1] = true;
for(int i = 1; i <= n; i++) {
if(!isnt[i]) {
Primes.push_back(i);
for(int j = 2; i * j <= n; j++) {
isnt[i * j] = true;
}
}
}
}
signed main() {
#ifdef LOCAL
file();
#endif
init(N - 4);
// for(int i = 0; i < 25; i++) printf("%d\n", Primes[i]);
int T = rd();
while(T--) solve();
return 0;
}CF1474C - Array Destruction
总觉得我的做法复杂度不对。。
upd: 竟然是std？？？
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#pragma GCC optimize(2)
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e5 + 5;
int a[N];
multiset<int> S, vS;
void debug() {
for(auto it : S) cout << it << " ";
cout << endl;
}
vector<pair<int, int> > opt;
int n;
int solve2(int);
void solve1() {
vS.clear();
n = rd() * 2;
for(int i = 1; i <= n; i++) a[i] = rd();
for(int i = 1; i <= n; i++) vS.insert(a[i]);
sort(a + 1, a + n + 1);
for(int i = 1; i < n; i++) {
S.clear();
S = vS;
if(solve2(a[i])) return ;
}
puts("NO");
}
int solve2(int lucky) {
opt.clear();
int lstmax = *(--S.end());
S.erase(--S.end());
S.erase(S.find(lucky));
opt.push_back(make_pair(lstmax, lucky));
while(S.size()) {
auto umaxp = --S.end();
int umax = *umaxp;
multiset<int>::iterator it = S.find(lstmax - umax);
if(it != S.end()) ;
else return false;
if(umaxp == it) return false;
opt.push_back(make_pair(*it, umax));
S.erase(S.find(lstmax - umax));
S.erase(--S.end());
lstmax = umax;
}
puts("YES");
printf("%d\n", opt[0].first + opt[0].second);
for(int i = 0; i < n / 2; i++) {
printf("%d %d\n", opt[i].first, opt[i].second);
}
return true;
}
signed main() {
#ifdef LOCAL
file();
#endif
int T = rd();
while(T--) solve1();
return 0;
}P1967 [NOIP2013 提高组] 货车运输
建立最大生成树。
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e4 + 5, M = 5e4 + 4;
struct Edge {
int to, nxt, wei;
} Edge[M << 1];
int head[N], cnt;
void addEdge(int u, int v, int w) {
Edge[++cnt].to = v;
Edge[cnt].nxt = head[u];
head[u] = cnt;
Edge[cnt].wei = w;
}
class UnionSet {
public:
static const int N = ::N;
int fa[N];
UnionSet() {
for(int i = 1; i < N; i++) fa[i] = i;
}
int leader(int x) {
return fa[x] == x ? x : fa[x] = leader(fa[x]);
}
void merge(int x, int y) {
int fx = leader(x), fy = leader(y);
if(fx == fy) return ;
fa[fx] = fy;
}
} us;
struct Prepares {
int u, v, w;
bool operator<(const Prepares& a) const {
return w > a.w;
}
} pre[M];
int dep[N], f[N][21], minx[N][21], belongTo[N], vis[N];
void dfs1(int u, int fa, int depth) {
f[u][0] = fa; dep[u] = depth; vis[u] = 1;
for(int i = 1; i <= 20; i++) f[u][i] = f[f[u][i - 1]][i - 1];
for(int i = head[u]; i; i = Edge[i].nxt) {
const int v = Edge[i].to;
if(v == fa) continue;
// cout << u << " " << v << " " << Edge[i].wei << endl;
dfs1(v, u, depth + 1);
belongTo[v] = Edge[i].wei;
}
}
void dfs2(int u, int fa) {
minx[u][0] = belongTo[u];
for(int i = 1; i <= 20; i++) minx[u][i] = min(minx[u][i - 1], minx[f[u][i - 1]][i - 1]);
for(int i = head[u]; i; i = Edge[i].nxt) {
const int v = Edge[i].to;
if(v == fa) continue;
dfs2(v, u);
}
}
typedef pair<int, int> pi;
pi lca(int x, int y) {
int mx = 0x3f3f3f3f;
if(dep[x] < dep[y]) swap(x, y);
int dis = dep[x] - dep[y];
for(int i = 20; ~i; i--) if(dis & (1 << i)) mx = min(minx[x][i], mx), x = f[x][i];
if(x == y) return make_pair(x, mx);
for(int i = 20; ~i; i--) if(f[x][i] != f[y][i]) mx = min(mx, min(minx[x][i], minx[y][i])), x = f[x][i], y = f[y][i];
return make_pair(f[x][0], min(mx, min(minx[x][0], minx[y][0])));
}
signed main() {
#ifdef LOCAL
file();
#endif
memset(belongTo, 0x3f, sizeof belongTo);
int n = rd(), m = rd();
for(int i = 1; i <= m; i++) {
pre[i].u = rd();
pre[i].v = rd();
pre[i].w = rd();
}
sort(pre + 1, pre + m + 1);
for(int i = 1; i <= m; i++) {
if(us.leader(pre[i].u) == us.leader(pre[i].v)) continue;
us.merge(pre[i].u, pre[i].v);
addEdge(pre[i].u, pre[i].v, pre[i].w);
addEdge(pre[i].v, pre[i].u, pre[i].w);
}
for(int i = 1; i <= n; i++) if(!vis[i]) dfs1(i, 0, 1), dfs2(i, 0);
int Q = rd();
for(int i = 1; i <= Q; i++) {
int x = rd(), y = rd();
if(us.leader(x) != us.leader(y)) {
puts("-1");
} else {
pi res = lca(x, y);
printf("%d\n", res.second);
}
}
return 0;
}树剖题选
P3384 【模板】轻重链剖分
需要注意的是找
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e5 + 5;
int n, m, r, mod, a[N];
class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
public :
static const int N = ::N;
int val[N << 2], add[N << 2];
SegmentTree() {
ms(val);
ms(add);
}
void modify_add(int l, int r, int x, int p, int q, int v) {
if(p <= l && r <= q) {
add[x] = (add[x] + v) % mod;
val[x] = (val[x] + (r - l + 1) * v % mod) % mod;
return ;
}
MID; push_down(l, r, x);
if(p <= mid) modify_add(lson, p, q, v);
if(q > mid) modify_add(rson, p, q, v);
push_up(x);
}
void push_up(int x) {
val[x] = (val[x << 1] + val[x << 1 | 1]) % mod;
}
void push_down(int l, int r, int x) {
if(!add[x]) return ;
MID;
val[x << 1] = (val[x << 1] + (mid - l + 1) * add[x] % mod) % mod;
val[x << 1 | 1] = (val[x << 1 | 1] + (r - mid) * add[x] % mod) % mod;
add[x << 1] = (add[x << 1] + add[x]) % mod;
add[x << 1 | 1] = (add[x << 1 | 1] + add[x]) % mod;
add[x] = 0;
}
int query(int l, int r, int x, int p, int q) {
if(p <= l && r <= q)
return val[x];
MID; push_down(l, r, x);
int res = 0;
if(p <= mid) res = (res + query(lson, p, q)) % mod;
if(q > mid) res = (res + query(rson, p, q)) % mod;
return res;
}
} st;
struct Edge {
int to, nxt;
} Edge[N << 1];
int head[N], cnt;
void addEdge(int u, int v) {
Edge[++cnt].to = v;
Edge[cnt].nxt = head[u];
head[u] = cnt;
}
int dfn[N], dep[N], fa[N], sz[N], hs[N], top[N], idx;
void dfs1(int u, int d, int depth) {
dep[u] = depth; fa[u] = d; sz[u] = 1;
int maxs = 0;
for(int i = head[u]; i; i = Edge[i].nxt) {
const int v = Edge[i].to;
if(v == d) continue;
dfs1(v, u, depth + 1);
sz[u] += sz[v];
if(sz[v] > maxs) maxs = sz[v], hs[u] = v;
}
}
void dfs2(int u, int tf) {
top[u] = tf;
dfn[u] = ++idx;
if(sz[u] == 1) return ;
dfs2(hs[u], tf);
for(int i = head[u]; i; i = Edge[i].nxt) {
const int &v = Edge[i].to;
if(v == fa[u] || v == hs[u]) continue;
dfs2(v, v);
}
}
int qRange(int x, int y) {
int res = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res = (res + st.query(1, n, 1, dfn[top[x]], dfn[x])) % mod; x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
return (res + st.query(1, n, 1, dfn[y], dfn[x])) % mod;
}
void mRange(int x, int y, int z) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
st.modify_add(1, n, 1, dfn[top[x]], dfn[x], z); x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
st.modify_add(1, n, 1, dfn[y], dfn[x], z);
}
signed main() {
#ifdef LOCAL
file();
#endif
n = rd(), m = rd(), r = rd(), mod = rd();
for(int i = 1; i <= n; i++) {
a[i] = rd();
}
for(int i = 1; i < n; i++) {
int u = rd(), v = rd();
addEdge(u, v); addEdge(v, u);
}
dfs1(r, r, 1);
dfs2(r, r);
for(int i = 1; i <= n; i++) {
st.modify_add(1, n, 1, dfn[i], dfn[i], a[i]);
}
for(int i = 1; i <= m; i++) {
int opt = rd();
if(opt == 1) {
int x = rd(), y = rd(), z = rd() % mod;
mRange(x, y, z);
} else if(opt == 2) {
int x = rd(), y = rd();
printf("%lld\n", qRange(x, y) % mod);
} else if(opt == 3) {
int x = rd(), z = rd() % mod;
st.modify_add(1, n, 1, dfn[x], dfn[x] + sz[x] - 1, z);
} else if(opt == 4) {
int x = rd();
// d(x); d(dfn[x]); d(dfn[x] + sz[x] - 1);
printf("%lld\n", st.query(1, n, 1, dfn[x], dfn[x] + sz[x] - 1) % mod);
}
}
return 0;
}P3178 [HAOI2015]树上操作
记录一段有问题的代码。如果跳到深度为
int qRange(int x) {
if(x == 1) return st.query(1, n, 1, id[1], id[1]);
int res = 0;
while(x != 1) {
res += st.query(1, n, 1, id[top[x]], id[x]);
x = fa[top[x]];
}
return res;
}#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 1e5 + 6;
class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
public :
static const int N = ::N;
int sum[N << 2], add[N << 2];
SegmentTree() {
ms(sum);
ms(add);
}
void push_up(int x) {
sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
void push_down(int l, int r, int x) {
if(!add[x]) return ;
MID;
add[x << 1] += add[x];
add[x << 1 | 1] += add[x];
sum[x << 1] += (mid - l + 1) * add[x];
sum[x << 1 | 1] += (r - mid) * add[x];
add[x] = 0;
}
void modify_add(int l, int r, int x, int p, int q, int v) {
if(p <= l && r <= q) {
add[x] += v;
sum[x] += (r - l + 1) * v;
return ;
}
MID; push_down(l, r, x);
if(p <= mid) modify_add(lson, p, q, v);
if(q > mid) modify_add(rson, p, q, v);
push_up(x);
}
int query(int l, int r, int x, int p, int q) {
if(p <= l && r <= q) return sum[x];
MID; push_down(l, r, x);
int res = 0;
if(p <= mid) res += query(lson, p, q);
if(q > mid) res += query(rson, p, q);
return res;
}
} st;
struct Edge {
int to, nxt;
} Edge[N << 1];
int head[N], cnt, n, m;
void addEdge(int u, int v) {
Edge[++cnt].to = v;
Edge[cnt].nxt = head[u];
head[u] = cnt;
}
int fa[N], dep[N], id[N], top[N], sz[N], hs[N], a[N], idx;
void dfs1(int u, int d, int depth) {
dep[u] = depth; fa[u] = d; sz[u] = 1; int mx = 0;
for(int i = head[u]; i; i = Edge[i].nxt) {
const int v = Edge[i].to;
if(v == d) continue;
dfs1(v, u, depth + 1);
sz[u] += sz[v];
if(sz[v] > mx) hs[u] = v, mx = sz[v];
}
}
void dfs2(int u, int tf) {
id[u] = ++idx; top[u] = tf;
if(sz[u] == 1) return ;
dfs2(hs[u], tf);
for(int i = head[u]; i; i = Edge[i].nxt) {
const int v = Edge[i].to;
if(v == fa[u] || v == hs[u]) continue;
dfs2(v, v);
}
}
int qRange(int x) {
int res = 0;
while(top[x] != 1) {
res += st.query(1, n, 1, id[top[x]], id[x]);
x = fa[top[x]];
}
return res + st.query(1, n, 1, 1, id[x]);
}
signed main() {
#ifdef LOCAL
file();
#endif
n = rd(), m = rd();
for(int i = 1; i <= n; i++) {
a[i] = rd();
}
for(int i = 1; i < n; i++) {
int u = rd(), v = rd();
addEdge(u, v); addEdge(v, u);
}
dfs1(1, 1, 1);
dfs2(1, 1);
for(int i = 1; i <= n; i++) st.modify_add(1, n, 1, id[i], id[i], a[i]);
for(int i = 1; i <= m; i++) {
int opt = rd();
if(opt == 1) {
int x = rd(), v = rd();
st.modify_add(1, n, 1, id[x], id[x], v);
} else if(opt == 2) {
int x = rd(), v = rd();
st.modify_add(1, n, 1, id[x], id[x] + sz[x] - 1, v);
} else if(opt == 3) {
int x = rd();
printf("%lld\n", qRange(x));
}
}
return 0;
}P2590 [ZJOI2008]树的统计
#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
int f = 1, val = 0; char ch = getchar();
while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
return f * val;
}
void file() {
freopen("in.in", "r", stdin);
//freopen("out.out", "w+", stdout);
}
const int N = 3e4 + 6;
class SegmentTree {
#define MID int mid = (l + r) >> 1
#define lson l, mid, x << 1
#define rson mid + 1, r, x << 1 | 1
public :
static const int N = ::N;
int sum[N << 2], add[N << 2], maxx[N << 2];
SegmentTree() {
ms(sum);
ms(add);
ms(maxx);
}
void push_up(int x) {
sum[x] = sum[x << 1] + sum[x << 1 | 1];
maxx[x] = max(maxx[x << 1], maxx[x << 1 | 1]);
}
void modify(int l, int r, int x, int p, int v) {
if(l == r) {
sum[x] = maxx[x] = v;
return ;
}
MID;
if(p <= mid) modify(lson, p, v);
if(p > mid) modify(rson, p, v);
push_up(x);
}
int query_sum(int l, int r, int x, int p, int q) {
if(p <= l && r <= q) return sum[x];
MID;
int res = 0;
if(p <= mid) res += query_sum(lson, p, q);
if(q > mid) res += query_sum(rson, p, q);
return res;
}
int query_max(int l, int r, int x, int p, int q) {
if(p <= l && r <= q) return maxx[x];
MID;
int res = 0xafafafafafafafaf;
if(p <= mid) res = max(res, query_max(lson, p, q));
if(q > mid) res = max(res, query_max(rson, p, q));
return res;
}
} st;
struct Edge {
int to, nxt;
} Edge[N << 1];
int head[N], cnt, n;
void addEdge(int u, int v) {
Edge[++cnt].to = v;
Edge[cnt].nxt = head[u];
head[u] = cnt;
}
int fa[N], dep[N], id[N], top[N], sz[N], hs[N], a[N], idx;
void dfs1(int u, int d, int depth) {
fa[u] = d; dep[u] = depth; sz[u] = 1; int mx = 0;
for(int i = head[u]; i; i = Edge[i].nxt) {
const int &v = Edge[i].to;
if(v == d) continue;
dfs1(v, u, depth + 1);
sz[u] += sz[v];
if(sz[v] > mx) mx = sz[v], hs[u] = v;
}
}
void dfs2(int u, int tf) {
id[u] = ++idx; top[u] = tf;
if(sz[u] == 1) return ;
dfs2(hs[u], tf);
for(int i = head[u]; i; i = Edge[i].nxt) {
const int &v = Edge[i].to;
if(v == fa[u] || v == hs[u]) continue;
dfs2(v, v);
}
}
int mRange(int x, int y) {
int res = 0xafafafafafafafaf;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res = max(res, st.query_max(1, n, 1, id[top[x]], id[x])); x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
return max(res, st.query_max(1, n, 1, id[y], id[x]));
}
int sRange(int x, int y) {
int res = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res += st.query_sum(1, n, 1, id[top[x]], id[x]); x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
return res + st.query_sum(1, n, 1, id[y], id[x]);
}
signed main() {
#ifdef LOCAL
file();
#endif
n = rd();
for(int i = 1; i < n; i++) {
int u = rd(), v = rd();
addEdge(u, v); addEdge(v, u);
}
for(int i = 1; i <= n; i++) a[i] = rd();
dfs1(1, 1, 1);
dfs2(1, 1);
for(int i = 1; i <= n; i++) st.modify(1, n, 1, id[i], a[i]);
int m = rd();
for(int i = 1; i <= m; i++) {
char opt[10];
scanf("%s", opt + 1);
if(opt[4] == 'X') { //QMAX
int u = rd(), v = rd();
printf("%lld\n", mRange(u, v));
} else if(opt[4] == 'N') { //CHANGE
int x = rd(), a = rd();
st.modify(1, n, 1, id[x], a);
} else if(opt[4] == 'M') { //QSUM
int u = rd(), v = rd();
printf("%lld\n", sRange(u, v));
}
}
return 0;
}
此处评论已关闭