## 【整体二分】AcWing268

### 传送门

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 233;
int o[maxn], b[maxn], lb[maxn], rb[maxn];
vector<int> pos[maxn];
ll p[maxn];
int ans[maxn];
int n, m, k;
struct rec{
int l, r; ll v;
}a[maxn];
ll c[2][maxn];
void add(int t, int x, ll v)
{
for(; x <= m; x += x & -x) c[t][x] += v;
}
{
ll res = 0;
for(; x; x -= x & 

## 我永远喜欢离线分治算法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 233;
struct rec{
int t, x, y, z;
}a[maxn], lb[maxn], rb[maxn];
unordered_map<int,int> ump, rg;
set<int> st;
int n, m;
int seq[maxn];
int c[maxn], tot;
{
for(; x <= n; x += x & -x) 

## 【kmp】AcWing160

### 传送门

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 233;
int n, m, q;
char a[maxn], b[maxn];
int ne[maxn], f[maxn];
int main()
{
cin >> n >> m >> q;
cin >> a + 1 >> b + 1;
ne[1] = 0;
for(int i =2, j = 0; i <= m; i++)
{
while(j > 

## 【CDQ分治】AcWing 267

### 然后玄学的地方出现了

#include<bits/stdc++.h>
using namespace std;
//unordered_map<int,int> ump;
const int maxn = 1e6 + 233;
struct Node{
int x, y, t, v;
}q[maxn], b[maxn];
int ans[maxn], c[maxn], tot = 0, idx[maxn];
int ump[maxn * 2];
inline void add(int x, int v)
{
for(; x <= tot; x += x & -x) c[x] += v;
}
{
int res = 0;


## 【有根树最小表示】AcWing 157

### 传送门

#include<bits/stdc++.h>
using namespace std;
string s1, s2;
string gao(string &s, int &i)
{
vector<string> v;
i++;
while(s[i] == '0')
{
v.push_back(gao(s, i));
}
i++;
string res = "0";
sort(v.begin(), v.end());
for(auto &str: v) res += str;
res += "1";
return res;
}
int main()
{
int T; cin >> T;
while(T--)
{
cin >> s1 >> s2;
s1 = '0' + s1 + '1';
s2 = '0' + s2 + '1';
int n = 0, m = 0;


## 【逆序对/贪心】BZOJ4240

### 传送门

#include<bits/stdc++.h>
using namespace std;
const int maxn  = 3e5 + 233;
typedef long long ll;
typedef pair<int,int> pii;
vector<pii> a;
int n;
int c[maxn];
{
for(; x <= n; x += x & -x) c[x] += 1;
}
{
int res = 0;
for(; x; x -= x & -x) res += c[x];
return res;
}
int main()
{
cin 

## 【树形dp】acwing758

### 传送门

f[i][0]代表i节点的儿子都符合条件，且 i 点所在的连通块白色点。
f[i][1]代表i节点的儿子都符合条件，且 i 点所在的连通块没有白色点

1. 当 i 点是白色点的时候。f[i][1] = 0因为他不可能存在一个连通块内并且不包含白色。f[i][0]由其所有的儿子的方案累乘。具体来说，对于一个儿子j，可以选择切割这条边，+f[j][0]，也可以不切这条边 +f[j][1]

f[i][1] = 0

f[i][0]=\prod{(f[j][0] + f[j][1])}

1. 当 i 点是黑色点的时候。f[i][1]也是同理由其儿子选择切割与不切割转移来，f[i][0]则是由贡献白点的儿子转移，由于只能有一个儿子贡献白点，其他儿子贡献的是全黑点的连通块，所以各个儿子贡献之间是加法关系

f[i][1] = \prod{(f[j][0] + f[j][1])}

f[i][0] = \sum f[j][1] * \prod\limits_{i != j}{f[j][0]}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233;
const ll mod = 1000000007;
int e[maxn * 2], h[maxn], pre[maxn * 2], c[maxn], cnt;


## 【数论】等边三角形 gym-101845E

### 传送门

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int main()
{
int n; cin >> n;
for(int i = 1; i <= n + 1; i++)
for(int j = 1; j <= i; j++) a.push_back(i << 16 | j);
long long ans = 0;
for(int i = 0; i < a.size(); i++)
{
int x = a[i] >> 16, y = a[i] & ((1 << 16) - 1);
for(int j = i; j < a.size(); j++)


## 【莫队算法】区间众数

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn = 2e5 + 233;
set<int> st;
unordered_map<int,int> ump;
int block, n, m, a[maxn], ans[maxn], cnt, p[maxn], num[maxn];
struct qs{
int l, r, idx;
}b[maxn];
bool cmp(const qs &x, const qs &y)
{
return (x.l / block) == (y.l / block) ? x.r < y.r : x.l < y.l;
}
inline void pls(int x)
{
num[p[a[x]]++]--;
int t = p[a[x]];
num[t] ++;
if(t 

## 【字符串hash（动态维护）】bzoj2124

### 字符串hash实际上是一种前缀和

#### 回忆字符串hash的离线构造

f[i] = f[i – 1] * base + s[i]

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 1e4 + 233;
int n;
ull p[maxn];
struct BIT{
ull c[maxn];
void init()
{
memset(c, 0, sizeof c);
}
for(int i = x; i <= n;