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>
