20250721
P5357 【模板】AC 自动机 - 洛谷
主要是构建fail树
/*
我们可以知道的是，当访问一个点x时，接下来需要跳转其fail[x]，以此类推，如果在某个fail[x]上出现了一个字符串，那么相应的统计次数应该加1，然后当访问到fail[x]时，又要继续访问fail[fail[x]]造成了一个点多次访问的情况
那么我们可以看出如果我们访问到了一个点x,那么接下来他的fail点都会继续访问到，那么我们其实可以构造一个fail树，当匹配主串的时候仅让siz[u]++,而不跳转他的fail[u],然后再遍历完主串的时候我们得到了每个点访问的次数，构建fail树，根据树的特性遍历求出哪些点访问过了多少次，这样就能把时间控制在O(S + T + n)内，S是模式串的总长度，T是主串长度，n是模式串个数
*/
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 1e6 + 10, INF = 0x3f3f3f3f;int n;int cnt[N], ne[N], ch[N][30], idx;string s[N], t;int match[N]; // 统计第几个字符串出现在哪个idx上int siz[N]; // 每个点访问过的次数vector vec[N]; // 构建fail树void insert(string x, int id){ int p = 0; rep(0, x.size() - 1) { int j = x[i] - \'a\'; if(!ch[p][j]) ch[p][j] = ++idx; p = ch[p][j]; } cnt[p]++; match[id] = p;}void built(){ queue q; rep(0, 25) if(ch[0][i]) q.push(ch[0][i]); while(!q.empty()) { auto u = q.front(); q.pop(); for(int i = 0; i <= 25; i++) { int v = ch[u][i]; if(v) ne[v] = ch[ne[u]][i], q.push(v); else ch[u][i] = ch[ne[u]][i]; } }}void dfs(int u){ for(auto it : vec[u]) { dfs(it); siz[u] += siz[it]; }}void query(string x){ for (int k = 0, i = 0; k < x.size(); k++) { i = ch[i][x[k] - \'a\']; ++siz[i]; } rep(1, idx) vec[ne[i]].pb(i); dfs(0); rep(1, n) cout << siz[match[i]] <> n; rep(1, n) { cin >> s[i]; insert(s[i], i); } built(); cin >> t; query(t);}signed main(){ IOS; int T = 1; // cin >> T; while(T --) solve(); return 0;}https://codeforces.com/problemset/problem/2109/B
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;int n, m, a, b;void solve(){ cin >> n >> m >> a >> b; if(n == 2 && m == 2) { cout << 2 << \'\\n\'; return; } int t1 = ceil(log2(n)), t2 = ceil(log2(m)); int c1 = ceil(log2(min(a, n - a + 1))), c2 = ceil(log2(min(b, m - b + 1))); cout << min(t1 + c2, c1 + t2) + 1 <> T; while(T --) solve(); return 0;}https://codeforces.com/problemset/problem/2108/B
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;int n, x;void solve(){ cin >> n >> x; int cnt = 0; int tx = x; if(n == 1 && x == 0) { cout << -1 << \'\\n\'; return; } while(tx) { if(tx & 1) cnt++; tx /= 2; } if(n <= cnt) { cout << x << \'\\n\'; return; } else { if((n - cnt) % 2 == 0) cout << x + (n - cnt) < 1) cout << x + (n - cnt) + 1 << \'\\n\'; else cout << n + 3 <> T; while(T --) solve(); return 0;}Contest Login
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;int n, x, y;int count(int a){ int ans = 0; while(a) { if(a & 1) ans ++; a /= 2; } return ans;}void solve(){ cin >> n >> x >> y; if(x == y) { cout << 0 << \'\\n\'; return; } if(count(x) == count(y) || lowbit(x) == lowbit(y)) { cout << 1 << \"\\n\"; return; } cout << 2 <> T; while(T --) solve(); return 0;}Contest Login
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 2e5 + 10, INF = 0x3f3f3f3f;void solve(){ int n; scanf(\"%d\", &n); printf(\"%.4f\\n\", 1.0 * 3 * n / 2);}signed main(){ // IOS; int T = 1; cin >> T; while(T --) solve(); return 0;}二维偏序问题
Contest Login
/*
题目的意思就是对于一个数在a[]数组中的位置为i,在b[]数组中的位置为j，那么我们的结果就是(i - 1) + (j - 1) + 前面重复的部分
主要就是重复的部分怎么求呢？如果有重复的部分，那么是不是一个数x在a[]和b[]中的下标分别小于i, j。这就是一个典型的二维偏序问题。经典的做法就是树状数组
我们对于a[]原封不动，对于b[]数组，记录下b[]元素所在b[]数组中的位置。我们开始遍历a[]数组，得到a[]数组的(i - 1) + (j - 1)这个值。根据遍历a[]数组的顺序就可以知道，a[]数组后面的元素所要加的值肯定有a[]数组前面的元素，那么我们在把a[i]在b[]数组中出现的位置用BIT统计上，这样如果我们访问a[]的下一个元素的时候，如果这个元素在b[]中的位置在j之后，那么因为我们刚才更新了BIT就能直接通过BIT减去重复的，如果在j之前的话，那么就没有影响。。。以此类推
*/
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 1e6 + 10, INF = 0x3f3f3f3f;int n;int a[N], b[N], p[N], ans[N];struct BIT{ int s[N]; BIT() { init(); } void init() { memset(s, 0, sizeof s); } void update(int poi, int val) { for (int i = poi; i 0; i -= lowbit(i)) ans += s[i]; return ans; }};BIT bit;void solve(){ cin >> n; bit.init(); rep(1, n) cin >> a[i]; rep(1, n) { cin >> b[i]; p[b[i]] = i; } rep(1, n) { int res = (i - 1) + (p[a[i]] - 1); res -= bit.query(p[a[i]]); // cout << ans << \" \\n\"[i == n]; ans[a[i]] = res; bit.update(p[a[i]], 1); } rep(1, n) cout << ans[i] <> T; while(T --) solve(); return 0;}P2163 [SHOI2007] 园丁的烦恼 - 洛谷
核心思想就是因为我们统计的是每一个矩形框内的点的个数，那么难免会用到二维前缀和，但是有时候我们的二维前缀和的数组需要开太大题目不支持。我们在计算二维前缀和的时候会用到一个公式，那么我们就就可以根据扫描线的原理，先将所有的点按照x从大到小的顺序排序，然后将满足x条件的点全加进BIT中，但是加进来的是这个点的纵坐标，然后因为我们将访问一个矩阵变成了4个矩阵的而访问和，那么我们在对每一个访问矩阵的操作的时候就可以直接计算满足其y的点的个数，本质还是通过BIT的离线处理
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 1e7 + 5, INF = 0x3f3f3f3f;int n, m;struct BIT{ int s[N]; BIT() { init(); } void init() { memset(s, 0, sizeof s); } void update(int poi, int val) { for (int i = poi; i 0; i -= lowbit(i)) ans += s[i]; return ans; }} bit;vector vec;vector qu;int ans[(int)5e5 + 10];void solve(){ cin >> n >> m; rep(1, n) { int a, b; cin >> a >> b; ++a, ++b; vec.pb({a, b}); } rep(1, m) { int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; ++x1, ++y1, ++x2, ++y2; qu.pb({x2, y2, 1, i}); qu.pb({x1 - 1, y2, -1, i}); qu.pb({x2, y1 - 1, -1, i}); qu.pb({x1 - 1, y1 - 1, 1, i}); } sort(vec.begin(), vec.end()); sort(qu.begin(), qu.end()); int cur = 0; for(auto [x, y, c, id] : qu) { while(cur < n && vec[cur].first <= x) bit.update(vec[cur].second, 1), cur++; ans[id] += bit.query(y) * c; } rep(1, m) cout << ans[i] <> T; while(T --) solve(); return 0;}P3755 [CQOI2017] 老C的任务 - 洛谷
加了离散化的，就是关键是一定要注意树状数组的大小问题。
#includeusing namespace std;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);#define lowbit(x) (x & (-x))#define int long long#define rep(l, r) for(int i = l; i <= r; i++)#define pb push_backtypedef pair PII;typedef pair PDD;typedef pair PID;typedef tuple TUP;const int N = 1e5 + 10, INF = 0x3f3f3f3f;int n, m;int maxlen;vector<array> vec;vector que;vector vy;map mp;int ans[N];struct BIT{ int s[N * 10]; BIT() { init(); } void init() { memset(s, 0, sizeof s); } void update(int poi, int val) { for (int i = poi; i 0; i -= lowbit(i)) ans += s[i]; return ans; }} bit;void solve(){ cin >> n >> m; rep(1, n) { int a, b, c; cin >> a >> b >> c; vec.pb({a, b, c}); vy.pb(b); } rep(1, m) { int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2; que.pb({x1 - 1, y1 - 1, 1, i}); que.pb({x2, y2, 1, i}); que.pb({x1 - 1, y2, -1, i}); que.pb({x2, y1 - 1, -1, i}); vy.pb(y2), vy.pb(y1 - 1); } sort(vec.begin(), vec.end()); sort(vy.begin(), vy.end()); sort(que.begin(), que.end()); vy.erase(unique(vy.begin(), vy.end()), vy.end()); maxlen = vy.size(); rep(0, vy.size() - 1) mp[vy[i]] = i + 1; int cur = 0; for(auto [x, y, c, id] : que) { while(cur < n && vec[cur][0] <= x) { bit.update(mp[vec[cur][1]], vec[cur][2]); cur++; } ans[id] += c * bit.query(mp[y]); } rep(1, m) cout << ans[i] <> T; while(T --) solve(); return 0;}
