数学
快速幂
ll qmi(ll a,ll b,ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
快速乘
ll a,b,p;
ll qmimul(ll a, ll b, ll p)
{
ll ans=0;
a %= p;
for(; b; b >>= 1)
{
if(b & 1)
ans += a, ans %= p;
a += a, a %= p;
}
return ans;
}
void solve()
{
cin>>a>>b>>p; cout<<qmimul(a,b,p)<<endl;
}
数论分块
void solve()
{
ll n, ans = 0; cin>>n;
for(ll l = 1; l <= n; l++)
{
ll d = n / l, r = n / d;
// ans + ...
l = r;
}
return;
}
枚举子集，超集
void solve()
{
int n; cin>>n;
// 枚举子集
for(int i = 1; i < (1 << n); i++)
for(int j = i; j; j = (j - 1) & i)
{
}
// 枚举超集
for(int i = 0; i < (1 << n); i++)
for(int j = i; ; j = (j + 1) | i)
{
if(j == (1 << n) - 1)
break;
}
}
矩阵乘法
const int mod = 1e9+7;
const int N = 200;
int n, m;
long long a[N + 1][N + 1], f[N + 1];
void aa()
{
long long w[N + 1][N + 1];
memset(w, 0, sizeof w);
for(int i = 1; i <= N; i++)
for(int k = 1; k <= N; k++)
if(a[i][k])
for(int j = 1; j <= N; j++)
if(a[k][j])
w[i][j] += a[i][k] * a[k][j], w[i][j] %= mod;
memcpy(a, w, sizeof a);
}
void fa()
{
long long w[N + 1];
memset(w, 0, sizeof w);
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
w[i] += f[j] * a[j][i], w[i] %= mod;
memcpy(f, w, sizeof f);
}
void matrixpow(int k)
{
for(; k; k /= 2)
{
if(k & 1)
fa();
aa();
}
}
void solve()
{
cin>>n>>m;
ll k; cin>>k;
// construct Martix
matrixpow(k);
cout<<f[ ]<<endl;
return;
}
筛法 & 质数
线性筛
int tot, p[N], pr[N];
void prime(int n)
{
for (int i = 2; i <= n; i++)
{
if (!p[i]) p[i] = i, pr[++tot] = i;
for (int j = 1; j <= tot && pr[j] * i <= n; j++) {
p[pr[j] * i] = pr[j];
if(p[i] == pr[j]) break;
}
}
}
埃式筛
int tot, p[N], pr[N];
void prime(int n)
{
for(int i = 2; i <= n; i++)
{
if(p[i]) continue;
pr[++tot] = i;
for(int j = i; j <= n / i; j++) p[i * j] = 1;
}
}
质因数分解
void primer(int x)
{
for (int i = 2; i <= x / i; i++)
{
if (x % i == 0)
{
int s = 0;
while (x % i == 0)
{
x = x / i;
s++;
}
cout << i << " " << s << endl;
}
}
if (x > 1) cout << x << " " << 1 << endl;
cout << endl;
}
欧拉函数
int n;
void solve()
{
cin>>n;
int ans = n;
vector<int> p;
for(int i = 2; i <= n / i; i++)
{
if(n % i == 0)
{
p.push_back(i);
while(n % i == 0) n /= i;
}
}
if(n != 1)
p.pb(n);
for(auto pri : p)
ans = ans / pri * (pri - 1);
cout<<ans<<endl;
return;
}
约数
最大公约数
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
求约数
vector<int> get_yueshu(int x)
{
vector<int> a;
for (int i = 1; i <= x / i; i++)
{
if (x % i == 0)
{
a.push_back(i);
if (i != x / i)
a.push_back(x / i);
}
}
sort(a.begin(), a.end());
return a;
}
扩展欧几里得1
\(ax - by = \gcd(a, b)\) 的最小非负整数解 \((x,y)\)
int exgcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int xx, yy;
int d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
int _;cin>>_;
while(_--)
{
int a, b, x, y;
cin>>a>>b;
int d = exgcd(a, b, x, y);
y = -y;
while(x < 0 || y < 0) x += b / d, y += a / d;
while(x >= b / d && y >= a / d) x -= b / d, y -= a / d;
cout<<x<<" "<<y<<endl;
}
}
扩展欧几里得2
\(ax + by = d\) 的 \(x\) 最小的解的非负整数解 \((x,y)\)
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b == 0)
{
x = 1; y = 0;
return a;
}
ll xx,yy;
ll d = exgcd(b, a % b, xx, yy);
x = yy;
y = xx - (a / b) * yy;
return d;
}
int main()
{
int _;cin>>_;
while(_--)
{
ll a, b, x, y, m;
scanf("%lld%lld%lld", &a, &b, &m);
ll d = exgcd(a, b, x, y);
if(m % d != 0)
{
puts("-1");
continue;
}
a /= d;
b /= d;
m /= d;
ll xx = (ll) x * (m % b) % b;
if(xx < 0) xx = xx + b;
ll yy = (ll)(m - a * xx) / b;
if(yy < 0)
puts("-1");
else
printf("%lld %lld\n", xx, yy);
}
}
逆元
线性
ll n, p, inv[N];
void solve()
{
cin>>p>>n;
inv[1] = 1;
for(int i = 2; i <= n; i++)
inv[i] = (p - p / i) * inv[p % i] % p;
return;
}
快速幂求逆元
qmi(a, mod - 2, mod)
组合数
\(O(N^2)\)
int n,c[N][N];
void init()
{
for(int i=0;i<=2000;i++)
for(int j=0;j<=i;j++)
if(j==0) c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
void solve()
{
int a,b; cin>>a>>b;
cout<<c[a][b]<<endl;
}
O(N)
int n;
ll f[N],infact[N];
void init()
{
f[0] = infact[0] = 1;
for(int i = 1; i <= 100000; i++)
{
f[i] = i * f[i - 1] % mod;
infact[i] = infact[i - 1] * 1ll * qmi(i, mod-2, mod) % mod;
}
}
void solve()
{
int a,b; cin>>a>>b;
cout<<(f[a] * infact[b] % mod * infact[a - b] % mod)<<endl;
}
Lucas \(O(\log_pNp\log_p)\)
int C(int a, int b, int p)
{
if (b > a) return 0;
int res = 1;
for (int i = 1, j = a; i <= b; i ++, j -- )
{
res = (ll)res * j % p;
res = (ll)res * qmi(i, p - 2, p) % p;
}
return res;
}
int lucas(ll a, ll b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (ll)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
数据结构
单调栈
给定一个长度为 \(N\) 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 \(−1\)
。
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
while (tt && a[tt] >= x) tt--; //tt有，栈顶大于待入栈元素
if (tt == 0) cout << "-1 "; //第一个数，栈无
else cout << a[tt] << " "; //输出所求
a[++tt] = x; //入栈，不符合的话下一次while就清理掉了
}
return 0;
}
单调队列
滑动窗口
int main()
{
cin >> n>>k;
for (int i = 0; i < n; i++)
cin >> a[i];
int hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
if (hh <= tt && i - k + 1 > qq[hh]) hh++;//处理框框队尾,框框满了处理队尾
while (hh <= tt && a[qq[tt]] >= a[i]) tt--; //队首
qq[++tt] = i; //队列加入新下标
if (i >= k - 1) cout << a[qq[hh]]<<" "; //框框满了
}
cout << endl;
hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
if (hh <= tt && i - k + 1 > qq[hh]) hh++;
while (hh <= tt && a[qq[tt]] <= a[i]) tt--;
qq[++tt] = i;
if (i >= k - 1) cout << a[qq[hh]]<<" ";
}
return 0;
}
并查集
普通板子
int find(int x)
{
if (fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
封装DSU
struct DSU {
std::vector<int> p, siz;
DSU(int n) : p(n + 1), siz(n + 1, 1) { std::iota(p.begin(), p.end(), 0); }
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
siz[x] += siz[y];
p[y] = x;
return true;
}
int size(int x) { return siz[find(x)]; }
};
哈希
单哈希板子
const int p = 9999971, base = 101;
int n , m, c[N + 10], ha[N + 10], hb[N + 10];
char a[N + 10], b[N + 10];
int main()
{
cin>>n>>m;
cin>>a + 1>>b + 1;
c[0] = 1;
for(int i = 1; i <= 200000; i++)
c[i] = (c[i - 1] * base) % p;
for(int i = 1; i <= n; i++)
ha[i] = (ha[i - 1] * base + a[i] - 'a') % p;
for(int i = 1; i <= m; i++)
hb[i] = (hb[i - 1] * base + b[i] - 'a') % p;
int ans = 0;
for(int i = 1; i + m - 1 <= n; i++)
if((ha[i + m - 1] - 1ll * ha[i - 1] * c[m] % p + p) % p == hb[m])
++ans;
cout<<ans<<endl;
return 0;
}
双哈希封装
typedef pair<long long, long long> pll;
struct DoubleStringHash
{
vector<long long> h1, h2, w1, w2;
long long base1 = 131, base2 = 13331;
long long p1 = 1e9 + 7, p2 = 1e9 + 9;
void init(string s) {
int len = s.size();
s = " " + s;
h1.resize(len + 1), w1.resize(len + 1);
h2.resize(len + 1), w2.resize(len + 1);
h1[0] = 0, w1[0] = 1;
h2[0] = 0, w2[0] = 1;
for(int i = 1; i <= len; i++) {
h1[i] = (h1[i - 1] * base1 + s[i]) % p1, w1[i] = w1[i - 1] * base1 % p1;
h2[i] = (h2[i - 1] * base2 + s[i]) % p2, w2[i] = w2[i - 1] * base2 % p2;
}
}
pll get(int l, int r) {
return {(h1[r] - h1[l - 1] * w1[r - l + 1] % p1 + p1) % p1, (h2[r] - h2[l - 1] * w2[r - l + 1] % p2 + p2) % p2};
}
};
Trie tree
普通板子
bool isend[N];
int n, m, nxt[N][26], cnt;
void solve()
{
cin>>n;
for(int i = 1; i <= n; i++)
{
string s; cin>>s;
int len = s.size(), now = 0;
for(int j = 0; j < len; j++)
{
int x = s[j] - 'a';
if(!nxt[now][x])
nxt[now][x] = ++cnt;
now = nxt[now][x];
}
isend[now] = true;
}
cin>>m;
for(int i = 1; i <= m; i++)
{
string s; cin>>s;
int len = s.size(), now = 0;
bool ok = true;
for(int j = 0; j < len; j++)
{
int x = s[j] - 'a';
if(!nxt[now][x])
{
ok = false;
break;
}
now = nxt[now][x];
}
if(ok)
if(!isend[now])
ok = false;
if(ok)
cout<<1<<endl;
else cout<<0<<endl;
}
return;
}
封装
struct trie
{
int nxt[500010][26], cnt;
bool isend[500010]; // 该结点结尾的字符串是否存在
void insert(string s) { // 插入字符串
int now = 0;
int l = s.size();
for (int i = 0; i < l; i++)
{
int x = s[i] - 'a';
if (!nxt[now][x]) nxt[now][x] = ++cnt; // 如果没有，就添加结点
now = nxt[now][x];
}
isend[now] = 1;
}
bool find(string s) { // 查找字符串
int now = 0;
int l = s.size();
for (int i = 0; i < l; i++) {
int x = s[i] - 'a';
if (!nxt[now][x]) return 0;
now = nxt[now][x];
}
return isend[now];
}
}tr;
void solve()
{
int n; cin>>n;
for(int i = 1; i <= n; i++)
{
string s; cin>>s;
tr.insert(s);
}
cin>>n;
for(int i = 1; i <= n; i++)
{
string s; cin>>s;
if(tr.find(s))
cout<<1<<endl;
else cout<<0<<endl;
}
return;
}
KMP
int nxt[N];
void solve()
{
string a, b; cin>>a>>b;
int n = a.size(), m = b.size();
a = "?" + a, b = "?" + b;
vector<int> ans;
for(int i = 2, j = 0; i <= n; i++)
{
while(j && a[i] != a[j + 1]) j = nxt[j];
if(a[i] == a[j + 1]) j++;
nxt[i] = j;
}
for(int i = 1, j = 0; i <= m; i++)
{
while(j == n || (j && b[i] != a[j + 1])) j = nxt[j];
if(b[i] == a[j + 1]) j++;
if(j == n)
ans.pb(i - n + 1);
}
}
树状数组
普通模板
int n,q;
ll tr[N], a[N];
void modify(int x, ll s)
{
for(; x <= n; x += x & -x)
tr[x] += s;
}
ll query(int x)
{
ll res = 0;
for(; x; x -= x & -x)
res += c[x];
return res;
}
dls封装
template<class T>
struct BIT {
T c[N];
int size;
void resize(int s) { size = s;}
T query(int x) { // 1 ... x
assert(x <= size);
T s = 0;
for (; x; x -= x & (-x)) {
s += c[x];
}
return s;
}
void modify(int x, T s) { // a[x] += s
assert(x != 0);
for (; x <= size; x += x & (-x)) {
c[x] += s;
}
}
};
BIT<ll> c1, c2;
线段树
线段树框架
struct info
{
// ...
};
struct tag
{
// ...
};
info operator + (const info &a, const info &b)
{
info t;
// ...
return t;
}
struct segtree
{
struct info val;
struct tag tag;
int sz; // ...
}seg[N * 4];
void update(int id)
{
// ...
}
void settag(int id, int tag)
{
// ...
// 更新val，tag
}
void pushdown(int id)
{
if(seg[id].tag != null)
{
settag(id * 2, seg[id].tag.tag);
settag(id * 2 + 1, seg[id].tag.tag);
seg[id].tag = null;
}
}
void build(int id, int l, int r)
{
seg[id].sz = r - l + 1;
if(l == r)
{
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void change(int id, int l, int r, int pos, struct tag tag)
{
if(l == r)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(pos <= mid)
change(id * 2, l, mid, pos, tag);
else change(id * 2 + 1, mid + 1, r, pos ,tag);
update(id);
}
void modify(int id, int l, int r, int ql, int qr, struct tag tag)
{
if(l == ql && r == qr)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(id * 2, l, mid, ql, qr, tag);
else if(ql > mid)
modify(id * 2 + 1, mid + 1, r, ql, qr, tag);
else
modify(id * 2, l, mid, ql, mid, tag),
modify(id * 2 + 1, mid +1 , r, mid + 1, qr, tag);
update(id);
}
info query(int id, int l, int r, int ql, int qr)
{
if(ql == l && qr == r)
{
return seg[id].val;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(id * 2, l, mid, ql, qr);
else if(ql > mid)
return query(id * 2 + 1, mid + 1, r, ql, qr);
else return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}
动态开点线段树
struct segtree
{
int l, r;
ll s, tag;
}seg[N * 30];
int n, m, tot = 1;
void update(int &id)
{
seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
}
void settag(int id, int sz, ll t)
{
seg[id].s += t * sz;
seg[id].tag += t;
}
void pushdown(int id, int l, int r)
{
if(seg[id].tag == 0) return;
if(seg[id].l == 0) seg[id].l = ++tot;
if(seg[id].r == 0) seg[id].r = ++tot;
int mid = (l + r) >> 1;
if(seg[id].l != 0)
settag(seg[id].l, mid - l + 1, seg[id].tag);
if(seg[id].r != 0)
settag(seg[id].r, r - mid, seg[id].tag);
seg[id].tag = 0;
}
void change(int &id, int l, int r, int pos, int val)
{
if(!id)
id = ++tot;
if(l == r)
{
seg[id].s = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
change(seg[id].l, l, mid, pos, val);
else
change(seg[id].r, mid + 1, r, pos, val);
update(id);
}
void modify(int &id, int l, int r, int ql, int qr, ll t)
{
if(!id)
id = ++tot;
if(l == ql && r == qr)
{
settag(id, r - l + 1, t);
return;
}
pushdown(id, l ,r);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(seg[id].l, l, mid, ql, qr, t);
else if(ql > mid)
modify(seg[id].r, mid + 1, r, ql, qr, t);
else
{
modify(seg[id].l, l, mid, ql, mid, t);
modify(seg[id].r, mid + 1, r, mid + 1, qr, t);
}
update(id);
}
ll query(int id, int l, int r, int ql, int qr)
{
if(!id)
id = ++tot;
if(l == ql && r == qr)
{
return seg[id].s;
}
pushdown(id, l, r);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(seg[id].l, l, mid, ql, qr);
else if(ql > mid)
return query(seg[id].r, mid + 1, r, ql, qr);
else
return query(seg[id].l, l, mid, ql, mid) +
query(seg[id].r , mid + 1, r, mid + 1, qr);
}
可持久化线段树第\(k\)小数
struct segtree
{
int l, r, s;
}seg[N * 30];
vector<int> vx;
int n, q, a[N], rt[N], tot;
void update(int id)
{
seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
}
int build(int l, int r)
{
int id = ++tot;
if(l == r)
return id;
int mid = (l + r) >> 1;
seg[id].l = build(l, mid);
seg[id].r = build(mid + 1, r);
return id;
}
int change(int u, int l, int r, int pos)
{
int id = ++tot;
seg[id] = seg[u];
if(l == r)
{
seg[id].s++;
return id;
}
int mid = (l + r) >> 1;
if(pos <= mid)
seg[id].l = change(seg[u].l, l, mid, pos);
else
seg[id].r = change(seg[u].r, mid + 1, r, pos);
update(id);
return id;
}
int query(int v, int u, int l, int r, int x)
{
if(l == r)
return l;
int cnt = seg[seg[u].l].s - seg[seg[v].l].s;
int mid = (l + r) >> 1;
if(x <= cnt)
return query(seg[v].l, seg[u].l, l, mid, x);
else
return query(seg[v].r, seg[u].r, mid + 1, r, x - cnt);
}
void solve()
{
cin>>n>>q;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
vx.push_back(a[i]);
}
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
rt[0] = build(1, vx.size());
for(int i = 1; i <= n; i++)
rt[i] = change(rt[i - 1], 1, vx.size(), lower_bound(vx.begin(), vx.end(), a[i]) - vx.begin() + 1);
while(q--)
{
int l, r, k; cin>>l>>r>>k;
cout<<vx[query(rt[l - 1], rt[r], 1, vx.size(), k) - 1]<<endl;
}
}
可持久化线段树前\(k\)大之和
int n, m, q, tot, rt[N], a[N];
ll mi[N];
vector<int> vx;
struct segtree
{
int l, r, cnt;
ll s, val;
}seg[N * 30];
void update(int id)
{
seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
seg[id].cnt = seg[seg[id].l].cnt + seg[seg[id].r].cnt;
}
int build(int l, int r)
{
int id = ++tot;
if(l == r)
{
return id;
}
int mid = (l + r) >> 1;
seg[id].l = build(l, mid);
seg[id].r = build(mid + 1, r);
update(id);
return id;
}
int change(int u, int l, int r, int pos)
{
int id = ++tot;
seg[id] = seg[u];
if(l == r)
{
seg[id].s = seg[id].s + vx[pos - 1];
seg[id].cnt = seg[id].cnt + 1;
seg[id].val = vx[l - 1];
return id;
}
int mid = (l + r) >> 1;
if(pos <= mid)
seg[id].l = change(seg[id].l, l, mid, pos);
else
seg[id].r = change(seg[id].r, mid + 1, r, pos);
update(id);
return id;
}
ll query(int v, int u, int l, int r, int k)
{
if(l == r)
{
return seg[u].val * k;
}
int mid = (l + r) >> 1;
int tmp = seg[seg[u].r].cnt - seg[seg[v].r].cnt;
if(tmp >= k)
return query(seg[v].r, seg[u].r, mid + 1, r, k);
else
return seg[seg[u].r].s - seg[seg[v].r].s
+ query(seg[v].l, seg[u].l, l, mid, k - tmp);
}
void solve()
{
tot = 0;
vx.clear();
cin>>n;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
vx.push_back(a[i]);
}
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
int m = vx.size();
rt[0] = build(1, m);
for(int i = 1; i <= n; i++)
{
int pos = lower_bound(vx.begin(), vx.end(), a[i]) - vx.begin() + 1;
rt[i] = change(rt[i - 1], 1, m, pos);
}
cin>>q;
for(int i = 1; i <= q; i++)
{
int l, r, k; cin>>l>>r>>k;
int mm = r - l + 1;
int x = l, y = l + mm - 1;
ll ans = query(rt[x - 1], rt[y], 1, m, k) + mi[mm];
cout<<ans<<'\n';
}
}
树链剖分 点权
// AC one more times
ll mod, w[N];
vector<int> e[N];
int n, root, q;
int tot, l[N], r[N], tid[N], top[N], bs[N], sz[N], f[N], dep[N];
void dfs1(int u, int fa)
{
sz[u] = 1;
dep[u] = dep[fa] + 1;
bs[u] = -1;
f[u] = fa;
for(auto v : e[u])
{
if(v == fa) continue;
dfs1(v, u);
sz[u] +=sz[v];
if(bs[u] == -1 || sz[v] > sz[bs[u]])
bs[u] = v;
}
}
void dfs2(int u,int t)
{
l[u] = ++tot;
tid[tot] = u;
top[u] = t;
if(bs[u] != -1)
dfs2(bs[u], t);
for(auto v : e[u])
{
if(v == bs[u] || v == f[u]) continue;
dfs2(v, v);
}
r[u] = tot;
}
struct segtree
{
ll s, tag, sz;
}seg[N * 4];
void update(int id)
{
seg[id].s = seg[id * 2].s + seg[id * 2 + 1].s;
seg[id].s %= mod;
seg[id].sz = seg[id * 2].sz + seg[id * 2 + 1].sz;
}
void settag(int id, ll tag)
{
seg[id].tag += tag;
seg[id].s += tag * seg[id].sz, seg[id].s %= mod;
}
void pushdown(int id)
{
if(seg[id].tag != 0)
{
settag(id * 2, seg[id].tag);
settag(id * 2 + 1, seg[id].tag);
seg[id].tag = 0;
}
}
void build(int id, int l, int r)
{
seg[id].sz = r - l + 1;
if(l == r)
{
seg[id].s = w[tid[l]];
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void modify(int id, int l, int r, int ql, int qr, ll tag)
{
if(l > r) return;
if(l == ql && r == qr)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(id * 2, l, mid, ql, qr, tag);
else if(ql > mid)
modify(id * 2 + 1, mid + 1, r, ql, qr, tag);
else
{
modify(id * 2, l, mid, ql, mid, tag);
modify(id * 2 + 1, mid + 1, r, mid + 1, qr, tag);
}
update(id);
}
ll query(int id, int l, int r, int ql, int qr)
{
if(l > r) return 0;
if(l == ql && r == qr)
{
return seg[id].s;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(id * 2, l, mid, ql, qr);
else if(ql > mid)
return query(id * 2 + 1, mid + 1, r, ql, qr);
else
{
return (query(id * 2, l, mid, ql, mid) +
query(id * 2 + 1, mid + 1, r, mid + 1, qr)) % mod;
}
update(id);
}
void modify(int u, int v, ll k)
{
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
modify(1, 1, n, l[top[u]], l[u], k);
u = f[top[u]];
}
else
{
modify(1, 1, n, l[top[v]], l[v], k);
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
modify(1, 1, n, l[v], l[u], k);
}
ll query(int u, int v)
{
ll ans = 0;
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
ans += query(1, 1, n, l[top[u]], l[u]);
ans %= mod;
u = f[top[u]];
}
else
{
ans += query(1, 1, n, l[top[v]], l[v]);
ans %= mod;
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
ans += query(1, 1, n, l[v], l[u]);
ans %= mod;
return ans;
}
void solve()
{
cin>>n>>q>>root>>mod;
for(int i = 1; i <= n; i++)
cin>>w[i];
for(int i = 1; i < n; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(root, 0);
dfs2(root, root);
build(1, 1, n);
while(q--)
{
int op; cin>>op;
if(op == 1)
{
int u, v; cin>>u>>v;
ll k; cin>>k;
modify(u, v, k);
}
else if(op == 2)
{
int u, v; cin>>u>>v;
cout<<query(u, v) % mod<<endl;
}
else if(op == 3)
{
int u; ll k;
cin>>u>>k;
modify(1, 1, n, l[u], r[u], k);
}
else if(op == 4)
{
int u; cin>>u;
cout<<query(1, 1, n, l[u], r[u]) % mod<<endl;
}
}
return;
}
树链剖分 边权下放
vector<PII> e[N];
int n, q;
int tot, l[N], r[N], tid[N], top[N], bs[N], sz[N], f[N], dep[N];
ll w[N];
pii edge[N];
void dfs1(int u, int fa)
{
sz[u] = 1;
dep[u] = dep[fa] + 1;
bs[u] = -1;
f[u] = fa;
for(auto v : e[u])
{
if(v.fi == fa) continue;
dfs1(v.fi, u);
w[v.fi] = v.se;
sz[u] +=sz[v.fi];
if(bs[u] == -1 || sz[v.fi] > sz[bs[u]])
bs[u] = v.fi;
}
}
void dfs2(int u,int t)
{
l[u] = ++tot;
tid[tot] = u;
top[u] = t;
if(bs[u] != -1)
dfs2(bs[u], t);
for(auto v : e[u])
{
if(v.fi == bs[u] || v.fi == f[u]) continue;
dfs2(v.fi, v.fi);
}
r[u] = tot;
}
struct info
{
ll s, mav, miv;
};
info operator + (const info &a, const info &b)
{
return (info){a.s + b.s, max(a.mav, b.mav), min(a.miv, b.miv)};
}
struct segtree
{
struct info val;
int tag;
}seg[N * 4];
void update(int id)
{
seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}
void settag(int id, int tag)
{
seg[id].tag += tag, seg[id].tag %= 2;
swap(seg[id].val.mav, seg[id].val.miv);
seg[id].val = {-seg[id].val.s, -seg[id].val.mav, -seg[id].val.miv};
}
void pushdown(int id)
{
if(seg[id].tag == 1)
{
settag(id * 2, seg[id].tag);
settag(id * 2 + 1, seg[id].tag);
seg[id].tag = 0;
}
}
void build(int id, int l, int r)
{
seg[id].tag = 0;
if(l == r)
{
seg[id].val = {w[tid[l]], w[tid[l]], w[tid[l]]};
return;
}
int mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
update(id);
}
void change(int id, int l, int r, int pos, ll ew)
{
if(l == r)
{
seg[id].val = {ew, ew, ew};
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(pos <= mid)
change(id * 2, l, mid, pos, ew);
else if(pos > mid)
change(id * 2 + 1, mid + 1, r, pos, ew);
update(id);
}
void modify(int id, int l, int r, int ql, int qr, ll tag)
{
if(ql > qr || l > r) return;
if(l == ql && r == qr)
{
settag(id, tag);
return;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
modify(id * 2, l, mid, ql, qr, tag);
else if(ql > mid)
modify(id * 2 + 1, mid + 1, r, ql, qr, tag);
else
{
modify(id * 2, l, mid, ql, mid, tag);
modify(id * 2 + 1, mid + 1, r, mid + 1, qr, tag);
}
update(id);
}
info query(int id, int l, int r, int ql, int qr)
{
if((ql > qr || l > r)) return (info){0, -100000000, 100000000};
if(l == ql && r == qr)
{
return seg[id].val;
}
pushdown(id);
int mid = (l + r) >> 1;
if(qr <= mid)
return query(id * 2, l, mid, ql, qr);
else if(ql > mid)
return query(id * 2 + 1, mid + 1, r, ql, qr);
else
{
return query(id * 2, l, mid, ql, mid) +
query(id * 2 + 1, mid + 1, r, mid + 1, qr);
}
update(id);
}
void modify(int u, int v, ll k)
{
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
modify(1, 1, n, l[top[u]], l[u], k);
u = f[top[u]];
}
else
{
modify(1, 1, n, l[top[v]], l[v], k);
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
modify(1, 1, n, l[v] + 1, l[u], k);
}
info query(int u, int v)
{
info ans = (info){0, -100000000, 100000000};
while(top[u] != top[v])
{
if(dep[top[u]] > dep[top[v]])
{
ans = ans + query(1, 1, n, l[top[u]], l[u]);
u = f[top[u]];
}
else
{
ans = ans + query(1, 1, n, l[top[v]], l[v]);
v = f[top[v]];
}
}
if(dep[u] < dep[v]) swap(u, v);
ans = ans + query(1, 1, n, l[v] + 1, l[u]);
return ans;
}
void solve()
{
cin>>n;
for(int i = 1; i < n; i++)
{
int u, v, w; cin>>u>>v>>w;
u++, v++;
edge[i] = {u, v};
e[u].push_bcak({v, w});
e[v].push_bcak({u, w});
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
cin>>q;
while(q--)
{
string op; cin>>op;
if(op == "C")
{
int i, w; cin>>i>>w;
int u = edge[i].fi, v = edge[i].se;
if(dep[u] < dep[v]) swap(u, v);
change(1, 1, n, l[u], w);
}
else if(op == "N")
{
int u, v;
cin>>u>>v;
u++, v++;
modify(u, v, 1);
}
else if(op == "SUM")
{
int u, v;
cin>>u>>v;
u++, v++;
cout<<query(u, v).s<<endl;
}
else if(op == "MAX")
{
int u, v;
cin>>u>>v;
u++, v++;
cout<<query(u, v).mav<<endl;
}
else if(op == "MIN")
{
int u, v;
cin>>u>>v;
u++, v++;
cout<<query(u, v).miv<<endl;
}
}
}
ST表
const int LOGN = 21;
const int N = 100000;
int f[N + 10][LOGN + 2], LOG[N + 10];
int n, m;
void pre()
{
LOG[1] = 0, LOG[2] = 1;
for(int i = 3; i <= N; i++)
LOG[i] = LOG[i / 2] + 1;
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>f[i][0];
pre();
for(int j = 1; j <= LOGN; j++)
{
for(int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
for(int i = 1; i <= m; i++)
{
cin>>x>>y;
int s = LOG[y - x + 1];
cout<<max(f[x][s], f[y - (1 << s) + 1][s])<<endl;
}
return;
}
LCA
#include<bits/stdc++.h>
using namespace std;
const int N = 5000010;
const int LOGN = 20;
int n, m, root, dep[N], fa[N][LOGN + 2];
vector<int> e[N];
void dfs(int u, int from)
{
dep[u] += dep[from] + 1;
for(auto v : e[u]) {
if(v == from) continue;
fa[v][0] = u;
dfs(v, u);
}
}
void lca_init()
{
for(int j = 1; j <= LOGN; j++)
for(int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for(int j = LOGN; j >= 0; j--)
if(d & (1 << j))
u = fa[u][j];
if(u == v) return u;
for(int j = LOGN; j >= 0; j--)
if(fa[u][j] != fa[v][j])
u = fa[u][j],v = fa[v][j];
return fa[u][0];
}
int main()
{
cin>>n>>m>>root;
for(int i = 2; i <= n; i++)
{
int u, v; cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(root, 0);
lca_init();
while(m--)
{
int u, v; cin>>u>>v;
cout<<lca_query(u, v)<<endl;
}
return 0;
}