二分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;
const int N = 50010;
string name[N];
string low[N], high[N];
string l[N], h[N];
int n;

int main() {
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> name[i];
        low[i] = name[i];
        sort(low[i].begin(), low[i].end());
        high[i] = low[i];
        reverse(high[i].begin(), high[i].end());
        l[i] = low[i], h[i] = high[i];
    }
    sort(l + 1, l + 1 + n);
    sort(h + 1, h + 1 + n);
    for(int i = 1; i <= n; ++i) {
        int pl = lower_bound(h + 1, h + 1 + n, low[i]) - h;
        int pr = upper_bound(l + 1, l + 1 + n, high[i]) - l - 1;
        // cout << high[i] << " " << pr << endl;
        // if(pl > n) pl = n;
        // if(pr > n) pr = n;
        cout << pl << " " << pr << endl;
    }

    return 0;
}

爆搜

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 10;
char g[N][N];
char path[N * N];
int n;
bool st[N][N];
int ans = 0;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int l, r;

void print(int idx) {
    for(int i = 1; i <= idx; ++i) putchar(path[i]);
    putchar('\n');
}

bool check(int idx) {
    int l = 0, r = 0;
    int i = 1;
    while(i <= idx && path[i] == '(') i++, l++;
    while(i <= idx && path[i] == ')') i++, r++;
    if(i <= idx) return false;
    if(l == r) ans = max(ans, l + r);
    if(l < r) return false;
    return true;
}
void dfs(int x, int y, int idx) {
    st[x][y] = true;
    path[idx] = g[x][y];

    // cout << x << " " << y << endl;
    // print(idx);
    // int t = check(idx);
    // cout << t << endl;
    if(!check(idx)) {
        st[x][y] = false;
        return;
    }
    for(int i = 0; i < 4; ++i) {
        int r = x + dx[i], c = y + dy[i];
        if(r <= 0 || c <= 0 || r > n || c > n || st[r][c]) continue;
        dfs(r, c, idx + 1);
    }
    st[x][y] = false;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%s", g[i] + 1);
    dfs(1, 1, 1);
    printf("%d\n", ans);
    return 0;
}

差分

1. 连续的相同的高度只能产生一种贡献，故可以缩为一点
2. 对于中间的元素，一个谷会对答案增加一个贡献，一个峰会减少一个贡献
3. 边界上的元素(i = 1 或 i = n) 为峰时减少一个贡献

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;
int c[N];

int main() {
    scanf("%d", &n);
    int minv = 0x3f3f3f3f;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    m = unique(b + 1, b + 1 + n) - b - 1;
    // 缩点
    int idx = 0;
    for(int i = 1; i <= n; ++i) {
        if(i < n && a[i] == a[i + 1]) {
            while(i < n && a[i] == a[i + 1]) i++;
        }
        a[++idx] = lower_bound(b + 1, b + 1 + m, a[i]) - b;;
    }
    n = idx;
    // for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
    // puts("");

    for(int i = 1; i <= n; ++i) {
        int t = a[i];
        if(i != 1 && i != n){
           if(a[i] < a[i - 1] && a[i] < a[i + 1]) c[t]++; 
           else if(a[i] > a[i - 1] && a[i] > a[i + 1]) c[t]--;
        } 
        else if(i == 1) {
            if(a[i] > a[i + 1]) c[t]--;
        }
        else if(i == n) {
            if(a[i] > a[i - 1]) c[t]--;
        }
    }
    int ans = 1, s = 1;
    for(int i = 1; i <= m; ++i) {
        s += c[i];
        ans = max(ans, s);
    }
    printf("%d\n", ans);
    return 0;
}

BFS

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second

using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
bool g[N][N];
int n, m;
int x1, y1;
bool st[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<PII> q;
int dist[N][N];

void dfs(int x, int y, int d) {
    for(int i = 0; i < 4; ++i) {
        int r = x + dx[i], c = y + dy[i];
        if(r < 0 || c < 0 || r > n || c > n || st[r][c]) continue;
        if(!g[r][c]) {
            dist[r][c] = d;
            st[r][c] = true;
            dfs(r, c, d);
        }
        else {
            dist[r][c] = d + 1;
            st[r][c] = true;
            q.push(make_pair(r, c));
        }
    }
}

int bfs() {
    q.push(make_pair(0, 0));
    st[0][0] = true;
    while(q.size()) {
        PII t = q.front();
        q.pop();
        dfs(t.x, t.y, dist[t.x][t.y]);
    }
    // for(int i = 1; i <= n; ++i){
    //     for(int j = 1; j <= n; ++j) {
    //         printf("%d %d %d\n", i, j, dist[i][j]);
    //     }
    // }
    return dist[x1][y1];
}

int main() {
    scanf("%d%d%d", &m, &x1, &y1);
    while(m--) {
        int x, y;
        scanf("%d%d", &x, &y);
        g[x][y] = true;
        n = max(n, x);
        n = max(n, y);
    }
    n++;
    printf("%d\n", bfs());
    return 0;
}

BFS

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#define x first
#define y second

using namespace std;
const int N = 55;
typedef pair<int, int> PII;
char g[N][N];
bool st[N][N];
int dist[N][N];

int n, m;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue<PII> q;
void init(int x, int y) {
    st[x][y] = true;
    dist[x][y] = 0;
    q.push(make_pair(x, y));
    for(int i = 0; i < 4; ++i) {
        int r = x + dx[i], c = y + dy[i];
        if(r <= 0 || c <= 0 || r > n || c > m || g[r][c] == '.' || st[r][c]) continue;
        init(r, c);
    }
}

int bfs(int x, int y) {
    init(x, y);
    while(q.size()) {
        PII t = q.front();
        q.pop();
        for(int i = 0; i < 4; ++i) {
            int r = t.x + dx[i], c = t.y + dy[i];
            if(r <= 0 || c <= 0 || r > n || c > m || st[r][c]) continue;
            if(g[r][c] == '.') {
                dist[r][c] = dist[t.x][t.y] + 1;
                q.push(make_pair(r, c));
                st[r][c] = true;
            }
            else return dist[t.x][t.y];
        }
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%s", g[i] + 1);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(g[i][j] == 'X') {
                printf("%d\n", bfs(i, j));
                return 0;
            }
        }
    }
    printf("%d\n", -1);

    return 0;
}

1. 差分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, k;

int main() {
    scanf("%d%d", &n, &k);
    int l, r;
    while(k--) {
        scanf("%d%d", &l, &r);
        a[l]++, a[r + 1]--;
    }
    for(int i = 1; i <= n; ++i) a[i] += a[i - 1];
    sort(a + 1, a + 1 + n);
    printf("%d\n", a[n + 1 >> 1]);

    return 0;
}

2. 树状数组

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int tr[N];
int n, k;
int a[N];

int lowbit(int x) {
    return x & -x;
}
void add(int pos, int x) {
    for(int i = pos; i <= n; i += lowbit(i)) tr[i] += x;
}
int query(int pos) {
    LL ans = 0;
    for(int i = pos; i; i -= lowbit(i)) ans += tr[i];
    return ans;
}
int main() {
    scanf("%d%d", &n, &k);
    int l, r;
    while(k--) {
        scanf("%d%d", &l, &r);
        add(l, 1);
        add(r + 1, -1);
    }
    for(int i = 1; i <= n; ++i) a[i] = query(i);
    sort(a + 1, a + 1 + n);
    printf("%d\n", a[n + 1 >> 1]);
    return 0;
}

暴力

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100;
typedef long long LL;
char a[N], b[N];
int n, m;

LL cal(char s[], int n, int base, int add, int pos) {
    LL ans = 0;
    for(int i = 1; i <= n; ++i) {
        char c = s[i] - '0';
        if(pos == i) c = (c + add) % base;
        ans = ans * base + c;
    }
    return ans;
}

bool check(int x, int y) {
    LL t1 = cal(a, n, 2, 1, x);
    LL t2 = cal(b, m, 3, 1, y);
    LL t3 = cal(b, m, 3, 2, y);
    return t1 == t2 || t1 == t3;
}

LL cal() {
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(check(i, j)) {
                return cal(a, n, 2, 1, i);
            }
        }
    }
    return -1;
}

int main() {
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1);
    m = strlen(b + 1);
    printf("%d\n", cal());

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 1e5 + 10;

struct Node {
    int son[2], p;
    int v;
    int size, lazy;
    void init(int _v, int _p) {
        v = _v;
        p = _p;
        size = 1;
    }
}tr[N];
int root, idx;
int n, m;

void pushup(int u) {
    int l = tr[u].son[0], r = tr[u].son[1];
    tr[u].size = tr[l].size + tr[r].size + 1;
}

void pushdown(int u) {
    if(tr[u].lazy) {
        int& l = tr[u].son[0];
        int& r = tr[u].son[1];
        swap(l, r);
        tr[l].lazy ^= 1;
        tr[r].lazy ^= 1;
        tr[u].lazy = 0;
    }
}

void rotate(int x) {
    int y = tr[x].p, z = tr[y].p;
    int k = x == tr[y].son[1];// k = 0, x是左子节点，k = 1, x是右子节点

    tr[z].son[y == tr[z].son[1]] = x, tr[x].p = z;
    tr[y].son[k] = tr[x].son[k ^ 1], tr[tr[x].son[k ^ 1]].p = y;
    tr[x].son[k ^ 1] = y, tr[y].p = x;

    pushup(y);
    pushup(x);
}

// 将结点x旋转成k的子节点
void splay(int x, int k) {
    while(tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if(z != k) {
            // 折线关系两次x
            // 直线关系一次y一次x
            if((tr[y].son[1] == x) == (tr[z].son[1] == y)) rotate(y);
            else rotate(x);            
        }
        rotate(x);
    }
    if(!k) root = x;// 0号结点的子节点是根节点
}

void insert(int v) {
    int u = root, p = 0;
    // 寻找值v的真实位置
    while(u) p = u, u = tr[u].son[v > tr[u].v];

    u = ++idx;
    if(p) tr[p].son[v > tr[p].v] = u;
    tr[u].init(v, p);
    splay(u, 0);// 新结点旋转到0的下面
}
// 寻找序列种的第k个点，即中序遍历中第k个点
int get_k(int k) {
    int u = root;
    while(true) {
        pushdown(u);
        int l = tr[u].son[0], r = tr[u].son[1];
        if(tr[l].size >= k) u = l;
        else if(tr[l].size + 1 == k) return u;
        else k -= tr[l].size + 1, u = r;
    }
    return -1;
}
void print(int u) {
    pushdown(u);
    // 输出中序遍历
    if(tr[u].son[0]) print(tr[u].son[0]);
    if(tr[u].v >= 1 && tr[u].v <= n) printf("%d ", tr[u].v);
    if(tr[u].son[1]) print(tr[u].son[1]);
}

int main() {
    scanf("%d%d", &n, &m);
    // 多插入0和n+1作为哨兵
    for(int i = 0; i <= n + 1; ++i) insert(i);
    while(m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        // 前面多了一个哨兵0，所以翻转的区间的[l + 1, r + 1], 哨兵为l和r+2
        l = get_k(l);
        r = get_k(r + 2);
        // 将目标区间成r的左子树
        splay(l, 0);// 将l旋转成根
        splay(r, l); // 将r旋转到l下面
        //反转整棵左子树即可
        tr[tr[r].son[0]].lazy ^= 1;
    }
    print(root);
    return 0;
}

CDQ分治

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;

struct Data{
    int a, b, c;
    int cnt;
    int ans;
    bool operator < (const Data& rhs) const{
        if(a != rhs.a) return a < rhs.a;
        if(b != rhs.b) return b < rhs.b;
        return c < rhs.c;
    }

    bool operator == (const Data& rhs) const {
        return a == rhs.a && b == rhs.b && c == rhs.c;
    }
}a[N], t[N];
int n, m;
int ans[M];
int tr[M];

int lowbit(int x) {
    return x & -x;
}

void add(int pos, int x) {
    for(int i = pos; i <= m; i += lowbit(i)) {
        tr[i] += x;
    }
}

int query(int pos) {
    int ans = 0;
    for(int i = pos; i; i -= lowbit(i)) {
        ans += tr[i];
    }
    return ans;
}

void cdq(int l, int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    int k = 0;
    int i = l, j = mid + 1;
    while(i <= mid && j <= r) {
        if(a[i].b <= a[j].b) {
            add(a[i].c, a[i].cnt);// i的c加入进去
            t[k++] = a[i++];
        }
        else {
            // 计算前面有多少个i满足要求
            a[j].ans += query(a[j].c);
            t[k++] = a[j++];
        }
    }
    while(i <= mid) {
        add(a[i].c, a[i].cnt);
        t[k++] = a[i++];
    }
    while(j <= r) {
        a[j].ans += query(a[j].c);
        t[k++] = a[j++];
    }
    // 恢复现场
    for(int i = l; i <= mid; ++i) add(a[i].c, -a[i].cnt);
    // 归并
    for(int i = l, j = 0; i <= r; ++i, ++j) a[i] = t[j];
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c), a[i].cnt = 1;
    sort(a + 1, a + 1 + n);
    int k = 0;
    for(int i = 1; i <= n; ++i) {
        if(a[i] == a[i - 1]) a[k].cnt++;
        else a[++k] = a[i];
    }
    // n = k;
    cdq(1, k);
    for(int i = 1; i <= k; ++i) ans[a[i].ans + a[i].cnt - 1] += a[i].cnt; // 相同的点也要记录
    for(int i = 0; i < n; ++i) printf("%d\n", ans[i]);

    return 0;
}

dsu on tree

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
typedef long long LL;
int n;
int color[N], son[N], sz[N], cnt[N];
int h[N], e[M], ne[M], idx;
LL ans[N];
int mx;
LL sum;

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

void dfs_son(int u, int fa) {
    sz[u] = 1;
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == fa) continue;
        dfs_son(j, u);
        sz[u] += sz[j];
        if(sz[j] > sz[son[u]]) son[u] = j;
    }
    // cout << u << " " << son[u] << endl;
}

void update(int u, int fa, int sign, int pson) {
    int c = color[u];
    cnt[c] += sign;
    if(cnt[c] > mx) mx = cnt[c], sum = c;
    else if(cnt[c] == mx)sum += c;
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == fa || j == pson) continue;
        update(j, u, sign, pson);
    }
}

void dfs(int u, int fa, int type) {
    for(int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if(j == fa || j == son[u]) continue;
        dfs(j, u, 0);
    }
    if(son[u]) dfs(son[u], u, 1);
    update(u, fa, 1, son[u]);
    ans[u] = sum;
    // cout << u << " " << sum << endl;
    if(type == 0) update(u, fa, -1, 0), sum = mx = 0;
}


int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &color[i]);
    memset(h, -1, sizeof h);
    for(int i = 1; i < n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs_son(1, -1);
    dfs(1, -1, 1);
    for(int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
    putchar('\n');

    return 0;
}