HDU-5145 NPY and girls
题意
每个女孩所在的班级为 a [ i ] a[i] a[i]，NPY每次到一个班级只能拜访一个女孩，问NPY访问区间 [ l , r ] [l,r] [l,r] 里的女孩的访问方式总共有多少种
思路
NPY访问总次数应为 r − l + 1 r-l+1 r−l+1，对于每个女孩，就是在这几个位置中任意选择一个位置，即求组合数 对于在 x x x 班级的女孩，访问的次数为 C r − l + 1 c n t [ x ] C_{r-l+1}^{cnt[x]} Cr−l+1cnt[x] 则将所有的都乘起来，即结果 由于组合数 C n + 1 m + 1 = C n m ∗ n + 1 m + 1 C_{n+1}^{m+1} = C_{n}^{m}*\frac{n+1}{m+1} Cn+1m+1=Cnm∗m+1n+1 令 l e n = r − l + 1 len = r-l+1 len=r−l+1，即 若 x x x 班级的人数增加 1 1 1， p r e pre pre 为未增加前的结果，则现在的结果应为 r e s = p r e ∗ l e n ∗ 1 c n t [ i ] res = pre * len * \frac{1}{cnt[i]} res=pre∗len∗cnt[i]1 若 x x x 班级的人数减少 1 1 1， p r e pre pre 为未减少前的结果，则现在的结果应为 r e s = p r e ∗ c n t [ x ] ∗ 1 l e n res = pre * cnt[x] * \frac{1}{len} res=pre∗cnt[x]∗len1 利用莫队分块转移区间， O ( 1 ) O(1) O(1) 求得每次转移后的结果
代码
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; typedef long long ll; const int maxn = 3e4 + 5;; const ll mod = 1e9 + 7; int block; struct node{ int l, r, id; bool operator<(const node &_) const { return l/block == _.l/block ? r < _.r : l/block < _.l/block; } }q[maxn]; int a[maxn], res[maxn], cnt[maxn]; ll inv[maxn]; ll ans; void init() { inv[0] = inv[1] = 1; for(int i = 2; i < maxn; i++) inv[i] = (mod-mod/i) * inv[mod%i] % mod; } void add(ll num, int x) { cnt[a[x]]++; ans = 1ll * ans * inv[cnt[a[x]]] % mod * num % mod; } void del(ll num, int x) { ans = 1ll * ans * cnt[a[x]] % mod * inv[num] % mod; cnt[a[x]]--; } int main() { int T; init(); scanf("%d", &T); while(T--) { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 1; i <= m; ++i) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } block = sqrt(n + 0.0); sort(q + 1, q + 1 + m); memset(cnt, 0, sizeof(cnt)); int L = 1, R = 0; ll num = 0; ans = 1; for(int i = 1; i <= m; ++i) { int l = q[i].l, r = q[i].r; while(L > l) add(++num, --L); while(R < r) add(++num, ++R); while(L < l) del(num--, L++); while(R > r) del(num--, R--); res[q[i].id] = ans; } for(int i = 1; i <= m; ++i) printf("%d\n", res[i]); } return 0; }SPOJ-COT2 Count on a tree II
题意
给一棵树，问点 ( u , v ) (u, v) (u,v) 的简单路径上，有多少个不同的点值
思路
建议看洛谷题解 SP10707 COT2 - Count on a tree II 题解 第一篇挺容易理解的 就是将树转为线性结构
代码
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int maxn = 1e5 + 5;; const ll mod = 1e9 + 7; const int MAX_LOG = 20; int block; struct node{ int l, r, lc, id; bool operator<(const node &_) const { return l/block == _.l/block ? r < _.r : l/block < _.l/block; } }q[maxn]; vector<int> ed[maxn]; vector<int> vv; int fa[maxn][40], dep[maxn], dfn[maxn]; int res[maxn], cnt[maxn]; int st[maxn], en[maxn]; // 欧拉序 int vis[maxn]; // 是否在区间中 int a[maxn]; ll ans; int tol; int getid(int x) { return lower_bound(vv.begin(), vv.end(), x) - vv.begin() + 1; } void init(int n) { vv.clear(); tol = 0; memset(cnt, 0, sizeof(cnt)); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; ++i) ed[i].clear(); } void deal(int x) { if(vis[x] && --cnt[a[x]] == 0) ans--; else if(!vis[x] && cnt[a[x]]++ == 0) ans++; vis[x] ^= 1; // 是否在已计算的区间内 } void dfs(int u, int pre, int d) { dep[u] = d, st[u] = ++tol; dfn[tol] = u, fa[u][0] = pre; for(int i = 1; (1<<i) <= dep[u]; ++i) fa[u][i] = fa[fa[u][i-1]][i-1]; for(auto v : ed[u]) { if(v == pre) continue; dfs(v, u, d + 1); } en[u] = ++tol; dfn[tol] = u; } int lca(int u, int v) { if(dep[u] < dep[v]) swap(u, v); int x = dep[u] - dep[v]; for(int i = 0; i <= MAX_LOG; ++i) if((x >> i) & 1) u=fa[u][i]; if(u == v) return u; for(int i = MAX_LOG; i >= 0; --i) { if(fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i]; } return fa[u][0]; } void solve(int n, int m) { dfs(1, 0, 1); block = sqrt(2*n + 0.0); // 点个数 2n for(int i = 1, u, v; i <= m; ++i) { scanf("%d%d", &u, &v); int lc = lca(u, v); if(st[u] > st[v]) swap(u, v); q[i].id = i, q[i].lc = lc; if(lc == u) q[i].l=st[u], q[i].r=st[v]; // 同一条链上 else q[i].l=en[u], q[i].r=st[v]; // 不同链上 } sort(q + 1, q + 1 + m); sort(vv.begin(), vv.end()); vv.erase(unique(vv.begin(), vv.end()), vv.end()); for(int i = 1; i <= n; ++i) a[i] = getid(a[i]); int L = q[1].l, R = q[1].l-1; for(int i = 1; i <= m; ++i) { int l = q[i].l, r = q[i].r; while(L > l) deal(dfn[--L]); while(R < r) deal(dfn[++R]); while(L < l) deal(dfn[L++]); while(R > r) deal(dfn[R--]); res[q[i].id] = ans; if(cnt[a[q[i].lc]] == 0) res[q[i].id]++; // 算上lca的 } } int main() { int n, m; scanf("%d%d", &n, &m); init(n); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); vv.push_back(a[i]); } for(int i = 1, u, v; i < n; ++i) { scanf("%d%d", &u, &v); ed[u].push_back(v), ed[v].push_back(u); } solve(n, m); for(int i = 1; i <= m; ++i) printf("%d\n", res[i]); return 0; }NBUT-1457 Sona
题意
求区间 [ l , r ] [l, r] [l,r] 中， ∑ c n t [ x ] 3 ( x ∈ { a [ j ] ∣ l ≤ j ≤ r } ) \sum cnt[x]^3(x \in \{a[j] | l \leq j \leq r\}) ∑cnt[x]3(x∈{a[j]∣l≤j≤r})， c n t [ x ] cnt[x] cnt[x] 表示 x x x 的个数
思路
题意读懂的话就是简单的莫队模板，稍微改一下 （其实我也没读题，看样例猜的 先扣除当前的 c n t [ x ] cnt[x] cnt[x] 的贡献，再加上更改后的贡献 这题时间卡的有点紧，如果超时可以加加看快读，都开int然后再取模
代码
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int maxn = 1e5 + 5; const ll mod = 1e9 + 7; int block; struct node{ int l, r, id; bool operator<(const node &_) const { return l/block == _.l/block ? r < _.r : l/block < _.l/block; } }q[maxn]; vector<int> vv; ll res[maxn], cnt[maxn]; int a[maxn]; ll ans; inline int getid(int x) { return lower_bound(vv.begin(), vv.end(), x) - vv.begin() + 1; } ll cal(ll x) { return x * x * x; } void add(int x) { ans -= cal(cnt[a[x]]); cnt[a[x]] += 1; ans += cal(cnt[a[x]]); } void del(int x) { ans -= cal(cnt[a[x]]); cnt[a[x]] -= 1; ans += cal(cnt[a[x]]); } void solve(int n, int m) { block = sqrt(n + 0.0); sort(q + 1, q + 1 + m); sort(vv.begin(), vv.end()); vv.erase(unique(vv.begin(), vv.end()), vv.end()); for(int i = 1; i <= n; ++i) a[i] = getid(a[i]); int L = q[1].l, R = q[1].l-1; for(int i = 1; i <= m; ++i) { int l = q[i].l, r = q[i].r; while(L > l) add(--L); while(R < r) add(++R); while(L < l) del(L++); while(R > r) del(R--); res[q[i].id] = ans; } } int main() { int n, m; while(~scanf("%d", &n)) { vv.clear(); ans = 0; for(int i = 1; i <= n; ++i) cnt[i]=0; for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); vv.push_back(a[i]); } scanf("%d", &m); for(int i = 1; i <= m; ++i) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } solve(n, m); for(int i = 1; i <= m; ++i) printf("%lld\n", res[i]); } return 0; }HDU-5213 Lucky
题意
每次询问给两个区间 [ l , r ] , [ u , v ] [l, r], [u, v] [l,r],[u,v] x ∈ [ l , r ] , y ∈ [ u , v ] , x + y = = k x \in [l, r], y \in [u, v], x+y == k x∈[l,r],y∈[u,v],x+y==k，问这样的对数存在多少对， ( l ≤ r < u ≤ v ) (l \leq r < u \leq v) (l≤r<u≤v) 比如 [1 2 1 2], k = 3 k = 3 k=3 [ l , r ] = [ 1 , 3 ] , [ u , v ] = [ 2 , 4 ] [l,r]=[1,3], [u, v]=[2, 4] [l,r]=[1,3],[u,v]=[2,4] 存在的对有（这里写下标，看起来比较清晰） ( 1 , 2 ) ( 1 , 4 ) ( 2 , 3 ) ( 3 , 2 ) ( 3 , 4 ) (1, 2)(1,4)(2,3)(3,2)(3,4) (1,2)(1,4)(2,3)(3,2)(3,4)
思路
考虑莫队，但莫队每次计算的都是一个区间内的组合，那么将这两个区间先合并起来看 区间 [ l , v ] [l, v] [l,v] 这段的值可以看做以下几个部分组成 其实也就是容斥求解
代码
#include <algorithm> #include <iostream> #include <cstring> #include <cstdio> #include <cmath> #include <vector> using namespace std; typedef long long ll; const int maxn = 3e4 + 5; const ll mod = 1e9 + 7; int block; struct node{ int l, r, id, op; bool operator<(const node &_) const { return l/block == _.l/block ? r < _.r : l/block < _.l/block; } }q[maxn<<2]; int cnt[maxn<<2]; int a[maxn]; ll res[maxn]; ll ans; int k; void add(int x) { if(x >= k) return ; ans -= cnt[x] * cnt[k-x]; cnt[x]++; ans += cnt[x] * cnt[k-x]; } void del(int x) { if(x >= k) return ; ans -= cnt[x] * cnt[k-x]; cnt[x]--; ans += cnt[x] * cnt[k-x]; } void solve(int n, int m) { block = sqrt(n + 0.0); sort(q + 1, q + 1 + m); int L = q[1].l, R = q[1].l-1; for(int i = 1; i <= m; ++i) { int l = q[i].l, r = q[i].r; while(L > l) add(a[--L]); while(R < r) add(a[++R]); while(L < l) del(a[L++]); while(R > r) del(a[R--]); res[q[i].id] += ans * q[i].op; } } int main() { int n, m; while(~scanf("%d", &n)) { scanf("%d", &k); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); scanf("%d", &m); for(int i = 1, j = 1; i <= m; i++) { int l, r, u, v; scanf("%d%d%d%d", &l, &r, &u, &v); q[j].l = l, q[j].r = v, q[j].id = i, q[j].op = 1; j++; q[j].l = l, q[j].r = u-1, q[j].id = i, q[j].op = -1; j++; q[j].l = r+1, q[j].r = v, q[j].id = i, q[j].op = -1; j++; q[j].l = r+1, q[j].r = u-1, q[j].id = i, q[j].op = 1; j++; } ans = 0; memset(cnt, 0, sizeof(cnt)); memset(res, 0, sizeof(res)); solve(n, m*4); for(int i = 1; i <= m; ++i) printf("%lld\n", res[i]); } return 0; }