0_0_26434059_31910.cpp:1:3814: fatal error: GCC4.9.2/x86_64-w64-mingw32/include/c++/bits/stdc++.h>usin: Invalid argument
#include <bits/stdc++.h>using namespace std;const int maxn = 1e5 + 10;typedef long long LL;const LL mod = 1e9 + 7;int n, q;char s[maxn];struct Matrix{ LL v[3][3]; Matrix operator *(const Matrix &res){ Matrix ans; for(int i = 0; i <= 2; i++) { for(int j = 0; j <= 2; j++) { ans.v[i][j] = 0; for(int k = 0; k <= 2; k++) { ans.v[i][j] += (v[i][k] * res.v[k][j]) % mod; ans.v[i][j] %= mod; } } } return ans; } void rev(){//矩阵第一列与第二列交换，然后第一行与第二行交换 swap(v[0][0], v[1][1]); swap(v[1][0], v[0][1]); swap(v[0][2], v[1][2]); } };Matrix x1 = {1, 1, 1, 0, 1, 0, 0, 0, 1};//s[i]为0时的递推矩阵Matrix x2 = {1, 0, 0, 1, 1, 1, 0, 0, 1};//s[i]为1时的递推矩阵Matrix s1 = {1, 0, 0, 0, 0, 0, 1, 0, 0};//s[i]为0时的初始矩阵Matrix s2 = {0, 0, 0, 1, 0, 0, 1, 0, 0};//s[i]为0时的初始矩阵struct node{ int l, r; Matrix sum;//区间矩阵乘积 int add;//是否翻转，0表示不翻转，1表示翻转}Node[maxn<<2];void pushUp(int i){ int lson = i<<1; int rson = lson|1; Node[i].sum = Node[rson].sum * Node[lson].sum;}void pushDown(int i){ int lson = i<<1; int rson = lson|1; Node[lson].add ^= 1; Node[rson].add ^= 1; Node[lson].sum.rev(); Node[rson].sum.rev(); Node[i].add = 0;}void build(int i, int l, int r){ Node[i].l = l; Node[i].r = r; Node[i].add = 0; if(l == r) { if(s[l] == '0') Node[i].sum = x1; else Node[i].sum = x2; return; } int f = i; i <<= 1; int mid = (l + r)>>1; build(i, l, mid); build(i|1, mid + 1, r); pushUp(f);}void update(int i, int l, int r){ if(Node[i].l == l && Node[i].r == r) { Node[i].add ^= 1; Node[i].sum.rev(); return; } if(Node[i].add) pushDown(i); int f = i; i <<= 1; if(r <= Node[i].r) update(i, l, r); else if(l >= Node[i|1].l) update(i|1, l, r); else { update(i, l, Node[i].r); update(i|1, Node[i|1].l, r); } pushUp(f);}Matrix queryMatrix(int i, int l, int r){ if(Node[i].l == l && Node[i].r == r) { return Node[i].sum; } if(Node[i].add) pushDown(i); i <<= 1; if(r <= Node[i].r) return queryMatrix(i, l, r); else if(l >= Node[i|1].l) return queryMatrix(i|1, l, r); else { Matrix t1 = queryMatrix(i, l, Node[i].r); Matrix t2 = queryMatrix(i|1, Node[i|1].l, r); return t2 * t1; }}int queryId(int i, int loc){ if(Node[i].l == Node[i].r) { return Node[i].add; } if(Node[i].add) pushDown(i); i <<= 1; if(loc <= Node[i].r) return queryId(i, loc); else if(loc >= Node[i|1].l) return queryId(i|1, loc);}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &q); scanf("%s", s + 1); build(1, 1, n); int op, l, r; for(int i = 1; i <= q; i++) { scanf("%d%d%d", &op, &l, &r); if(op == 1) { update(1, l, r); } else { if(l == r) { printf("1\n"); continue; } int id = queryId(1, l); Matrix re = queryMatrix(1, l + 1, r); Matrix term; if(id == 0) { if(s[l] == '0') term = s1; else term = s2; } else { if(s[l] == '0') term = s2; else term = s1; } term = re * term; LL cnt = (term.v[0][0] + term.v[1][0]) % mod; printf("%lld\n", cnt); } } } return 0;
^
compilation terminated.
|
