正題

luogu 4428

---

題目大意

給你一個01串，讓你進行一下兩種操作：
1.將其中一位取反
2.問你某一段中有多少個子串滿足有一種排列方案，使得組成的二進制數是3的倍數

---

解題思路

不難發現，因為2%3=2，所以2的冪%3的結果按121212…的規律循環

如果一個子串中1的個數為偶數個，可以讓它們在相鄰位，這樣就可以被三整除

如果一個子串中1的個數為奇數個，那么要先拿出三個1，分開放，組成10101，這樣才能讓其被3整除

\\

那么就有了以下兩種情況：

1.1的個數為偶數
2.1的個數為奇數，且$nu{m}_1>1,nu{m}_0?2$

如果計算這兩種情況，會十分困難

那么考慮用合法方案數=總方案數-不合法方案數

不合法的用以下情況

1.1的個數為奇數，且0的個數小于2
2.只有1個1

\\
以上兩種情況可以用線段樹計算

每個位置維護以下信息：

1.$ld/r{d}_{0/1,0/1}$強行經過左/右端點且0的出現次數為0/1,1的出現次數為偶數/奇數
2.$lo/r{o}_{0/1/2}$，強行經過左/右端點且恰好出現1次，0的出現次數為0/1/大于2
3.s0,s1,l0,r0，0的個數，1的個數，以左端點為起點0的個數，以右端點為終點0的個數

然后計算不合法的，把01和10這兩種不合法的情況減掉

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ls x*2 #define rs x*2+1 #define N 100100 #define ll long long using namespace std; ll n, m, x, y, a[N]; struct node {ll ld[2][2], rd[2][2], lo[3], ro[3], s0, l0, r0, s1, s;void clean(){memset(ld, 0, sizeof(ld));memset(rd, 0, sizeof(rd));memset(lo, 0, sizeof(lo));memset(ro, 0, sizeof(ro));s1 = s0 = l0 = r0 = s = 0;}void add(ll x){clean();if (x) ld[0][1] = rd[0][1] = lo[0] = ro[0] = s1 = s = 1;else ld[1][0] = rd[1][0] = s0 = l0 = r0 = 1;return;} }T[N<<2]; node merge(node a, node b) {node c;c.clean();for (ll i = 0; i <= 1; ++i)for (ll j = 0; j <= 1; ++j){c.ld[i][j] += a.ld[i][j];//計算ld/rdc.rd[i][j] += b.rd[i][j];if (i >= a.s0) c.ld[i][j] += b.ld[i - a.s0][j^(a.s1&1)];//左邊的0不夠，右邊的也要算進去if (i >= b.s0) c.rd[i][j] += a.rd[i - b.s0][j^(b.s1&1)];}for (ll i = 0; i <= 2; ++i){c.lo[i] += a.lo[i];//計算lo/roc.ro[i] += b.ro[i];if (!a.s1) c.lo[min(2ll, i + a.s0)] += b.lo[i];//左邊沒有1，右邊的也要算進去if (!b.s1) c.ro[min(2ll, i + b.s0)] += a.ro[i];}if (a.s1 == 1 && b.l0)//左邊只有1個1，右邊的0也要算進去{if (!a.s0) c.lo[1]++, c.lo[2] += b.l0 - 1;//10的情況只有1個0，其他都有2個以上的0else c.lo[2] += b.l0;}if (b.s1 == 1 && a.r0){if (!b.s0) c.ro[1]++, c.ro[2] += a.r0 - 1;else c.ro[2] += a.r0;}c.s0 = a.s0 + b.s0;c.s1 = a.s1 + b.s1;c.l0 = a.s1 ? a.l0 : a.l0 + b.l0;//左邊全是0，右邊的也要算進去c.r0 = b.s1 ? b.r0 : b.r0 + a.r0;c.s = a.s + b.s;//子區間的c.s += a.rd[0][0] * (b.ld[0][1] + b.ld[1][1]);//奇數個1，且0的個數小于2c.s += a.rd[0][1] * (b.ld[0][0] + b.ld[1][0]);c.s += a.rd[1][0] * b.ld[0][1];c.s += a.rd[1][1] * b.ld[0][0];if (a.r0) c.s += a.r0 * (b.lo[0] + b.lo[1] + b.lo[2]) - b.lo[0];//只有1個1的，要減去0+1的情況，因為0的個數小于2，前面有計算過if (b.l0) c.s += b.l0 * (a.ro[0] + a.ro[1] + a.ro[2]) - a.ro[0];return c; } void build(ll x, ll l, ll r)//線段樹 {if (l == r){T[x].add(a[l]);return;}ll mid = l + r >> 1;build(ls, l, mid);build(rs, mid + 1, r);T[x] = merge(T[ls], T[rs]);return; } void change(ll x, ll l, ll r, ll y, ll z) {if (l == r){T[x].add(z);return;}ll mid = l + r >> 1;if (y <= mid) change(ls, l, mid, y, z);else change(rs, mid + 1, r, y, z);T[x] = merge(T[ls], T[rs]);return; } node ask(ll x, ll L, ll R, ll l, ll r) {if (L == l && R == r) return T[x];ll mid = L + R >> 1;if (r <= mid) return ask(ls, L, mid, l, r);else if (l > mid) return ask(rs, mid + 1, R, l, r);else return merge(ask(ls, L, mid, l, mid), ask(rs, mid + 1, R, mid + 1, r)); } int main() {scanf("%lld", &n);for (ll i = 1; i <= n; ++i)scanf("%lld", &a[i]);build(1, 1, n);scanf("%lld", &m);while(m--){scanf("%lld", &x);if (x == 1){scanf("%lld", &x);a[x] ^= 1;change(1, 1, n, x, a[x]);}else{scanf("%lld%lld", &x, &y);printf("%lld\n", (y - x + 1) * (y - x + 2) / 2 - ask(1, 1, n, x, y).s);//總方案數減去不合法方案數}}return 0; }

總結

以上是生活随笔為你收集整理的【线段树】二进制（luogu 4428）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。