G@rage

传送门

其实整体二分就是在二分答案的同时把询问也二分了。排除询问不可能的值域。

树状数组可以区间更新单点查询，不要傻傻地去写区间更新区间查询的树桩上数组。。。

#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 ask(int t, int x)
{
    ll res = 0;
    for(; x; x -= x & 

传送门

我永远喜欢离线分治算法

题意不多说，带修改的区间第k大。

整体二分。

整体二分也叫基于值域的分治算法。

二分答案，先将整个序列的值域二分得mid。对于整个操作序列1~M，可以依次知道在操作区间Mi ：[ l , r ] <= mid 的值有多少个。具体来说就是利用一个树状数组，如果A[ i ] <= mid 那么树状数组add( i , 1)。 如果带有修改操作，那么就把修改拆成在位置 i 加一个数和减一个数。

如果对于第k大查询Mi，有cnt个数在区间内小于k，很明显如果cnt = k的话答案就在左值域里面。否则就在右值域里面。(注意，二分值域的意义就是二分查询的答案)

然后，对于这些询问进行分类。在左值域的询问和操作分一堆，在右值域的询问和操作分一堆。这是个分治的过程，继续往下递归这两类询问。直到值域二分的边界，所剩下的询问的答案就是这个值。

#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;
void add(int x, int v)
{
    for(; x <= n; x += x & -x) 

传送门

题意是说给定长度为n的字符串A，长度为m的字符串B，q个询问

每次询问有A的所有后缀里有多少个使得与B的前缀匹配长度恰好为K

在对A字符串做匹配的时候，本来 f[i] = j 表示的是A中以A[i]结尾的后缀与B的前缀的最大匹配长度。现在要改一下定义。f[x]表示匹配长度至少为x的有多少个位置。

当A中以A[i]结尾的字符串与B的最大匹配长度为j的时候，证明产生了一个匹配长度至少为j的后缀，但是不一定是恰好为j，因为此时的A[i]结尾字串并不是A数组的后缀。然后需要发现：匹配长度至少为next[j]的后缀的数量也增加了。

于是f函数的各个函数值之间是拓扑的关系。f[k] = \sum\limits_{next[j]=k} f[j]

于是匹配长度恰好为x的数量就是f[ x ] – f[ x + 1 ]

#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分治。

如果用二维BIT在线做的话，空间是不能承受的。所以考虑CDQ离线。

如果没有加数操作，只有询问，那么按照x排序，在y方向维护树状数组，就可以算出每个询问的答案。

现在有了加数操作，相当于时间变成了第三位。于是先按第三维排序，进行CDQ分治。每次分治之后把前一半的修改对后一半询问的影响看成一个离线询问。

然后玄学的地方出现了

把y坐标进行离散化。TLE

优化常数一，对每个y坐标改为它离散化后的相对大小，减小查询常数。TLE（甚至一组都过不了

优化常数二，把坐标离散化后再离线，对于每个下标 i 的坐标y，都存在idx[]数组里访问。TLE

优化常数三，把unorder_map改为了int数组，查询y坐标的时候直接访问数组，TLE

以上操作二和操作三是分开的，也就是说，两个理论查询复杂度O(1)的操作都是TLE

优化常数四，把操作二和操作三合并，理论上还是O(1)的而且常数还稍大了一点。AC……

#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;
}
inline int ask(int x)
{
    int res = 0;
    

传送门

最小表示这颗有根树，注意要加入哨兵元素

#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;
        

传送门

题意是说给定一个序列，只能交换相邻的两个数。问最后形成单峰序列（单调也是单峰）所需要的最小交换步数。

首先如果只需要单调数列，那么排序后，每个数在原序列中的下标所形成的逆序对就是交换次数。

由这个性质可以知道，旧序列的下标在新序列的逆序对就是答案。

接下来考虑如何形成单峰，做法是贪心，尽量形成少的逆序对。可以用树状数组动态维护。最开始的想法是说把尽量小的数往两边扔。但这样并没有很好的性质继续贪。
正确的做法是先考虑最大的数字。因为最终序列每个数字的相对位置都是固定的，所以先考虑最高的数字。

此时还需要发现一个性质：在一个序列（无论这个序列如何调整顺序）的两端加入一个数，所形成的新的逆序对/顺序对是固定的

也就是说，考虑第k大数字的时候的时候，只需要比较加在第k – 1大的数字的左边还是右边。由于k – 1大的数字所形成的序列是连续的，那么就等于在序列两端加数字，使得产生尽量少的逆序对。而在序列内部的数字如何调整对于要新加入的数字在左边还是右边是没有影响的。此时可以发现贪心策略是正确的。

对于值一样大的数字，由于相同的值最后肯定是相对顺序的，所以在考虑逆序对的时候不需要考虑和相同数字所产生的逆序对。具体来说，就是把所有一样的数字的结果先算出来，再把他们加入树状数组。

#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];
void add(int x)
{
    for(; x <= n; x += x & -x) c[x] += 1;
}
int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
int main()
{
    cin 

传送门

题意是给一棵树，每个节点有颜色，只有白色和黑色，切成若干部分，使得每部分只有一个白色点。
求切割方案。

状态设计

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])}

2. 当 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]}

这里的由于需要 i != j 的乘法积，可以直接先全部乘起来，再分别除f[i][0]。但是由于有取模操作，并且模数很大且是一个质数，所以用逆元来代替除法。

不过xc大佬用的前缀后缀积，更简单但是开始的确是没想到。

#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;

传送门

题意是说个一个边长为n的等边三角形，由若干个边长为1的等边三角形拼起来。问有多少个点对，相连的直线经过交点。

把等边三角形看成一个等腰直角三角形，相当于变型一下。可以发现，当横纵坐标差值的gcd 1的时候，点对是符合条件的。

数据只有50。直接暴力塞点然后判断就好。
不过队友在比赛的时候写的搜索，不知为何炸了。

#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++)
        

就是区间众数。

一个数组num[x]存两个指针内有多少个x，一个数组cnt[y]存两个指针内数量为y的有多少个。

当一个数字x的num[x]即将变成0的时候，cnt[num[x]]-1。如果cnt[num[x]]为0，那么必定存在一个有某个数cnt[?] = cnt[num[x]] – 1；所以这样就可以完成O(1)的计算区间内的信息。

还是蛮有技巧的

#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