Codeforces Round #263 (Div. 1) A B C_html/css_WEB-ITnose

Codeforces Round #263 (Div. 1)

A:贪心，排个序，然后从后往前扫一遍，计算后缀和，之后在从左往右扫一遍计算答案

B：树形DP，0表示没有1，1表示有1，0遇到0必然合并，0遇到1也必然合并，1遇到0必然合并，1遇到1，必然切断，按照这样去转移即可

C：树状数组，再利用启发式合并，开一个l，r记录当前被子左右下标，和一个flip表示是否翻转

代码：

A：

#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>using namespace std;typedef long long ll;const int N = 300005;int n;ll a[N], sum[N];int main() {	scanf("%d", &n);ll ans = 0; 	for (int i = 0; i = 0; i--)		sum[i] = a[i] + sum[i + 1];			for (int i = 0; i   <br> B：  <p></p>  <p> </p>  <pre name="code" class="sycode">#include <cstdio>#include <cstring>#include <vector>#include <cstdlib>using namespace std;const int N = 100005;typedef long long ll;const ll MOD = 1000000007;int n, node[N];vector<int> g[N];ll dp[N][2];ll pow_mod(ll x, ll k) {    ll ans = 1;     while (k) {        if (k&1) ans = ans * x % MOD;        x = x * x % MOD;        k >>= 1;    }    return ans;}ll inv(ll x) {    return pow_mod(x, MOD - 2);}void init() {    scanf("%d", &n);    int u;    for (int i = 1; i   <br> C：  <p></p>  <p> </p>  <pre name="code" class="sycode">#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define lowbit(x) (x&(-x))const int N = 100005;int n, q, bit[N];void add(int x, int v) {    while (x = 1; i--) {                        add(r - 2 * i + 1, get(tr - a + i) - get(tr - a + i - 1));                        r--;                    }                }                else {                    for (int i = a; i >= 1; i--) {                        add(l + 2 * i - 1, get(tl + a - i) - get(tl + a - i - 1));                        l++;                    }                }            } else {                a = r - a - l + 1;                if (!flip) {                    for (int i = a; i >= 1; i--) {                        add(r - 2 * i + 1, get(tr - a + i) - get(tr - a + i - 1));                        r--;                    }                }                else {                    for (int i = a; i >= 1; i--) {                        add(l + 2 * i - 1, get(tl + a - i) - get(tl + a - i - 1));                        l++;                    }                }                flip ^= 1;            }        }        else {            scanf("%d", &b);            if (flip) {                a = r - a;                b = r - b;                swap(a, b);            } else {                a += l - 1;                 b += l - 1;            }            printf("%d\n", get(b) - get(a));        }    }    return 0;}</algorithm></cstring></cstdio>