GCD
直接枚举\(\text {GCD}\)，$\text {bitset} $维护。
CD
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<bitset>
#include<map>
#include<vector>
using namespace std;
#define Miuna printf ("dai suki...")
#define Mizuki signed
#define love (1209 & 322 & 901)
namespace LRH
{
template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
{
x = 0;
char f = 0, ch;
while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
do
{
x = (x << 1) + (x << 3) + (ch ^ 48);
} while (isdigit (ch = getchar ()));
if (f) x = -x;
}
int st[40], tp;
template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
{
if (x < 0) putchar ('-'), x = -x;
do
{
st[++ tp] = x % 10;
x /= 10;
} while (x);
while (tp) putchar (st[tp --] | 48);
if (f == 1) putchar ('\n');
if (!f) putchar (' ');
}
}using namespace LRH;
const int maxn = 3e4 + 10;
int n, m, q;
int u[maxn], v[maxn], w[maxn];
bitset <30020> Q[maxn];
vector <int> a[100010];
pair<int, int> po[300010];
map <pair <int, int>, int> mp;
int gcd (int x, int y)
{
while (y)
{
int t = x; x = y;
y = t % x;
}
return x;
}
int fa[maxn];
int fd (int x)
{
while (x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
void un (int x, int y)
{
int fx = fd (x), fy = fd (y);
if (fx != fy) fa[fx] = fy;
}
int main ()
{
freopen ("gcd.in", "r", stdin);
freopen ("gcd.out", "w", stdout);
in (n), in (m), in (q);
int g = 0, mx = 0;
for (int i = 1; i <= m; ++ i)
{
in (u[i]), in (v[i]), in (w[i]);
int z = sqrt (w[i]);
if (!g) g = w[i];
else g = gcd (w[i], g);
mx = max (mx, w[i]);
for (int J = 1; J <= z; ++ J) if (w[i] % J == 0)
{
a[J].push_back (i);
if (J * J != w[i]) a[w[i] / J].push_back (i);
}
}
for (int i = 1; i <= q; ++ i)
{
in (po[i].first), in (po[i].second);
Q[po[i].first].set (po[i].second);
mp[po[i]] = -1;
}
for (int i = 1; i <= n; ++ i) fa[i] = i;
for (int i = mx; i >= 1; i -= g)
{
bitset <30020> s, g;
for (auto J : a[i])
{
s.set (u[J]), s.set (v[J]);
un (u[J], v[J]);
}
for (int x = s._Find_first (); x != 30020; x = s._Find_next (x))
{
g = s & Q[x];
for (int y = g._Find_first (); y != 30020; y = g._Find_next (y)) if (fd (x) == fd (y)) mp[{x, y}] = i, Q[x].reset(y);
}
for (int x = s._Find_first (); x != 30020; x = s._Find_next (x)) fa[x] = x;
}
for (int i = 1; i <= q; ++ i) ot (mp[po[i]], 1);
return love;
}
简单题
经典套路题，做过4次了，发现\(\varphi(1e6)\)最多操作\(20\)次就变成\(1\)了，非常\(\text J\)，于是就可以线段树暴力单点修改了，上传一个\(y\)的最大值，如果整个区间最大值是\(1\)那么直接区间加\(1\)即可，否则继续递归修改
然而记得要驱魔
CD
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Miuna printf ("dai suki...")
#define Mizuki signed
#define love (1209 & 322 & 901)
namespace LRH
{
template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
{
x = 0;
char f = 0, ch;
while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
do
{
x = (x << 1) + (x << 3) + (ch ^ 48);
} while (isdigit (ch = getchar ()));
if (f) x = -x;
}
int st[40], tp;
template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
{
if (x < 0) putchar ('-'), x = -x;
do
{
st[++ tp] = x % 10;
x /= 10;
} while (x);
while (tp) putchar (st[tp --] | 48);
if (f == 1) putchar ('\n');
if (!f) putchar (' ');
}
}using namespace LRH;
typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 998244353;
int n, m;
int x[maxn], y[maxn];
int prime[maxn], phi[maxn], cnt;
bool v[maxn];
void shai ()
{
phi[1] = 1;
for (int i = 2; i <= 1e6; ++ i)
{
if (!v[i]) prime[++ cnt] = i, phi[i] = i - 1;
for (int J = 1; J <= cnt; ++ J)
{
int k = i * prime[J];
if (k > 1e6) break;
v[k] = 1;
if (i % prime[J] == 0)
{
phi[k] = phi[i] * prime[J];
break;
}
phi[k] = phi[i] * (prime[J] - 1);
}
}
}
struct miuna
{
ll sumy, sumx, y, lz;
}t[maxn << 2];
inline void pushup (int k)
{
t[k].sumx = t[k << 1].sumx + t[k << 1 | 1].sumx;
t[k].sumy = t[k << 1].sumy + t[k << 1 | 1].sumy;
t[k].y = max (t[k << 1].y, t[k << 1 | 1].y);
}
inline void pushdown (int k, int l, int r)
{
int mid = l + r >> 1;
(t[k << 1].sumx += t[k].lz * (mid - l + 1)) %= mod;
(t[k << 1].lz += t[k].lz) %= mod;
(t[k << 1 | 1].sumx += t[k].lz * (r - mid)) %= mod;
(t[k << 1 | 1].lz += t[k].lz) %= mod;
t[k].lz = 0;
}
void build (int k, int l, int r)
{
if (l == r)
{
t[k].sumx = x[l], t[k].y = y[l], t[k].sumy = y[l];
return;
}
int mid = l + r >> 1;
build (k << 1, l, mid);
build (k << 1 | 1, mid + 1, r);
pushup (k);
}
void update (int k, int l, int r, int L, int R)
{
if (L <= l && r <= R && t[k].y == 1)
{
(t[k].sumx += r - l + 1) %= mod;
t[k].lz ++;
return;
}
if (l == r)
{
(t[k].sumx += t[k].y) %= mod;
t[k].y = phi[t[k].y];
t[k].sumy = t[k].y;
return;
}
if (t[k].lz) pushdown (k, l, r);
int mid = l + r >> 1;
if (L <= mid) update (k << 1, l, mid, L, R);
if (R > mid) update (k << 1 | 1, mid + 1, r, L, R);
pushup (k);
}
ll query_x (int k, int l, int r, int L, int R)
{
if (L <= l && r <= R) return t[k].sumx;
int mid = l + r >> 1;
if (t[k].lz) pushdown (k, l, r);
ll res = 0;
if (L <= mid) res = query_x (k << 1, l, mid, L, R);
if (R > mid) (res += query_x (k << 1 | 1, mid + 1, r, L, R)) %= mod;
return res;
}
ll query_y (int k, int l, int r, int L, int R)
{
if (L <= l && r <= R) return t[k].sumy;
int mid = l + r >> 1;
if (t[k].lz) pushdown (k, l, r);
ll res = 0;
if (L <= mid) res = query_y (k << 1, l, mid, L, R);
if (R > mid) (res += query_y (k << 1 | 1, mid + 1, r, L, R)) %= mod;
return res;
}
int main ()
{
freopen ("simple.in", "r", stdin);
freopen ("simple.out", "w", stdout);
shai ();
in (n), in (m);
for (int i = 1; i <= n; ++ i)
{
in (x[i]), in (y[i]);
}
build (1, 1, n);
int op, l, r;
for (int i = 1; i <= m; ++ i)
{
in (op), in (l), in (r);
if (op == 1) update (1, 1, n, l, r);
else
{
ot (query_x (1, 1, n, l, r), 0);
ot (query_y (1, 1, n, l, r), 1);
}
}
return love;
}
建筑
设\(max_{x, y, xx, yy}\)表示以\((x, y)\)为左上角，\((xx, yy)\)为左下角的矩形中的最大值
\(sum_{x, y, xx, yy}\)同上
要求\(\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}\sum\limits_{xx=x}^{n}\sum\limits_{yy=y}^{m}(xx - x + 1) \times (yy - y +1)\times max_{x ,y, xx, yy} - sum_{x, y, xx, yy}\)
先考虑后半部分，单独考虑每个点的贡献，发现点\((i, J)\)被\(i \times j \times (n - i+ 1)\times(m - J + 1)\)个矩形包含，因此点\((i, J)\)被计算了\(i \times j \times (n - i+ 1)\times(m - J + 1)\)次，所以它的贡献是$$i \times j \times (n - i+ 1)\times(m - J + 1)\times a_{i,J}$$
可以\(O(nm)\)处理出来
然后考虑前半部分，可以把\((xx - x +1)\)提出来，于是变成了$$\sum\limits_{x=1}^{n} \sum\limits_{xx=x}^{n}(xx - x +1)\sum\limits_{y = 1}^{m}\sum\limits_{yy = y}^{m}(yy - y+ 1)\times max_{x, y, xx, yy} $$
然而没有什么卵用
然后就可以考虑把后面一部分优化，我们直接把一个矩形压缩成一个序列，这样就可以\(O(max(n,m))\)后面了
考虑怎么压缩，我们直接枚举矩形的高，然后直接把这几行压缩，每一列都取一个最大值作为序列的第\(i\)个元素
一个序列的情况就很简单了，直接单调栈处理出每个元素的最左端点和最右端点，然后就可以直接算每个元素的贡献了
怎么计算呢，当区间的左端点在\(i\)时，他的贡献是\(\sum\limits_{r = i}^{R_i}r \times a_i\)，若左端点左移一位，那么贡献就会变成\(\sum\limits_{r=i}^{Ri}(r+1)\times a_i\)，左移\(x\)位就是加\((r+x)\)，发现每左移一位，就会比上次多计算一个\((r_i-i+1)\times a_i\)，发现是等差数列，一共会左移\(L_i - 1\)次，于是当左端点左移到\(L_i\)时初始贡献就会被计算\(\frac{(i - L_i +1)\times (i - L_i)}{2}\)次，于是就可以直接算出来了，然后最后记得乘上矩形的高度，就没了
时间复杂度：由于\(n \times m \leq1e5\)所以\(n\)和\(m\)中必有一个小于等于\(\sqrt {nm}\)，令小的一个作为高，另一个作为宽，这样时间复杂度就是\(O(nm\sqrt{nm})\)了，读入\(n > m\)时翻转一下就可以
CD
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define Miuna printf ("dai suki...")
#define Mizuki signed
#define love (1209 & 322 & 901)
namespace LRH
{
template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
{
x = 0;
char f = 0, ch;
while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
do
{
x = (x << 1) + (x << 3) + (ch ^ 48);
} while (isdigit (ch = getchar ()));
if (f) x = -x;
}
int st[40], tp;
template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
{
if (x < 0) putchar ('-'), x = -x;
do
{
st[++ tp] = x % 10;
x /= 10;
} while (x);
while (tp) putchar (st[tp --] | 48);
if (f == 1) putchar ('\n');
if (!f) putchar (' ');
}
}using namespace LRH;
typedef long long ll;
#define G (r[i] - i + 1)
#define F (i - l[i] + 1)
const int maxn = 1e5 + 10;
#define int ll
int n, m;
int mp[400][maxn];
int l[maxn], r[maxn];
int stk[maxn], top;
int a[maxn];
ll ans = 0;
ll solve ()
{
for (int i = 1; i <= m; ++ i)
{
while (top && a[stk[top]] < a[i]) r[stk[top --]] = i - 1;
l[i] = stk[top] + 1;
stk[++ top] = i;
}
while (top) r[stk[top --]] = m;
ll res = 0;
for (int i = 1; i <= m; ++ i) res += (1ll * G * (G + 1) / 2 * (i - l[i] + 1) + F * (F - 1) / 2 * G) * a[i];
return res;
}
Mizuki main ()
{
freopen ("building.in", "r", stdin);
freopen ("building.out", "w", stdout);
in (n), in (m);
ll ans = 0;
if (n < m) for (int i = 1; i <= n; ++ i) for (int J = 1; J <= m; ++ J) in (mp[i][J]);
else for (int i = 1; i <= n; ++ i) for (int J = 1; J <= m; ++ J) in (mp[J][i]);
if (n > m) swap (n, m);
for (int i = 1; i <= n; ++ i) for (int J = 1; J <= m; ++ J) ans -= 1ll * i * J * (n - i + 1) * (m - J + 1) * mp[i][J];
for (int i = 1; i <= n; ++ i)
{
for (int J = 1; J <= m; ++ J) a[J] = 0;
for (int J = i; J <= n; ++ J)
{
for (int k = 1; k <= m; ++ k) a[k] = max (a[k], mp[J][k]);
ans += solve () * (J - i + 1);
}
}
ot (ans);
return love;
}
树上前缀和
注意到给的是随机生成的树，所以直接跳\(father\)就行
直接树上前缀和，然后\(dis_i+dis_J-dis_{lca_{i,J}}-dis_{fa_{lca_{i,J}}}\)即可
然而你也可以像我这个J一样写线段树
CD
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Miuna printf ("dai suki...")
#define Mizuki signed
#define love (1209 & 322 & 901)
namespace LRH
{
template <typename Shiodome_miuna> inline void in (Shiodome_miuna &x)
{
x = 0;
char f = 0, ch;
while (!isdigit (ch = getchar ())) if (ch == '-') f = 1;
do
{
x = (x << 1) + (x << 3) + (ch ^ 48);
} while (isdigit (ch = getchar ()));
if (f) x = -x;
}
int st[40], tp;
template <typename Shiodome_miuna> inline void ot (Shiodome_miuna x, int f = 2)
{
if (x < 0) putchar ('-'), x = -x;
do
{
st[++ tp] = x % 10;
x /= 10;
} while (x);
while (tp) putchar (st[tp --] | 48);
if (f == 1) putchar ('\n');
if (!f) putchar (' ');
}
}using namespace LRH;
const int maxn = 1e5 + 10;
int n, m;
int a[maxn];
struct miuna
{
int v, nt;
}e[maxn << 1];
int tot, head[maxn];
inline void add (int x, int y)
{
e[++ tot] = {y, head[x]};
head[x] = tot;
}
int siz[maxn], top[maxn], num[maxn], fa[maxn], son[maxn], val[maxn], tim, dep[maxn];
void dfs1 (int x, int dad)
{
fa[x] = dad;
dep[x] = dep[fa[x]] + 1;
siz[x] = 1;
for (int i = head[x]; i; i = e[i].nt)
{
int y = e[i].v;
if (y == dad) continue;
dfs1 (y, x);
siz[x] += siz[y];
if (siz[y] > siz[son[x]]) son[x] = y;
}
}
void dfs2 (int x, int tp)
{
top[x] = tp;
num[x] = ++ tim;
val[tim] = a[x];
if (son[x]) dfs2 (son[x], tp);
for (int i = head[x]; i; i = e[i].nt)
{
int y = e[i].v;
if (y == fa[x] || y == son[x]) continue;
dfs2 (y, y);
}
}
int t[maxn << 2];
inline void pushup (int k)
{
t[k] = t[k << 1] + t[k << 1 | 1];
}
void build (int k, int l, int r)
{
if (l == r)
{
t[k] = val[l];
return;
}
int mid = l + r >> 1;
build (k << 1, l, mid);
build (k << 1 | 1, mid + 1, r);
pushup (k);
}
int query (int k, int l, int r, int L, int R)
{
if (L <= l && r <= R) return t[k];
int mid = l + r >> 1;
int res = 0;
if (L <= mid) res = query (k << 1, l, mid, L, R);
if (R > mid) res += query (k << 1 | 1, mid + 1, r, L, R);
return res;
}
int q_ (int x, int y)
{
int ans = 0;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap (x, y);
ans += query (1, 1, n, num[top[x]], num[x]);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap (x, y);
ans += query (1, 1, n, num[x], num[y]);
return ans;
}
int main ()
{
freopen ("shuqianzhui.in", "r", stdin);
freopen ("shuqianzhui.out", "w", stdout);
in (n), in (m);
for (int i = 1; i <= n; ++ i) in (a[i]);
for (int i = 1, x, y; i < n; ++ i)
{
in (x), in (y);
add (x, y);
add (y, x);
}
dfs1 (1, 1);
dfs2 (1, 1);
build (1, 1, n);
for (int i = 1, x, y; i <= m; ++ i)
{
in (x), in (y);
ot (q_ (x, y), 1);
}
return love;
}
