Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

program NKBRACKE;
uses    math;
const   maxn=100005;
        oo=trunc(1e9);
        fi='';
        num:array['('..')'] of longint = (1,-1);
var     n,m,res,t,p,pos,l,r,ok,sl,sr:longint;
        s:ansistring;
        c:char;
        bit,a,sum:array[0..maxn] of longint;
        it,lazy:array[1..4*maxn] of longint;
        inp:text;

procedure buildIT(k,l,r,i,v:longint);
var     m:longint;
begin
        if (r<i) or (i<l) then exit;
        if l=r then begin
                it[k]:=v;
                exit;
        end;
        m:=(l+r) shr 1;
        buildIT(k shl 1,l,m,i,v);
        buildIT(k shl 1 or 1, m+1,r,i,v);
        it[k]:=min(it[k shl 1],it[k shl 1 or 1]);
end;

procedure updateBIT(i,v:longint);
begin
        while i<=n do begin
                inc(bit[i],v);
                i:=i+i and (-i);
        end;
end;

function getBIT(i:longint):longint;
var     sum:longint;
begin
        sum:=0;
        while i>0 do begin
                inc(sum,bit[i]);
                i:=i-i and (-i);
        end;
        exit(sum);
end;

procedure updateIT(k,l,r,i,j,v:longint);
var     m:longint;
begin
        if lazy[k]<>0 then begin
                if l<>r then begin
                        inc(lazy[k shl 1],lazy[k]);
                        inc(lazy[k shl 1 or 1],lazy[k]);
                end;
                inc(it[k],lazy[k]);
                lazy[k]:=0;
        end;
        if (l>r) or (r<i) or (j<l) then exit;
        if (i<=l) and (r<=j) then begin
                inc(it[k],v);
                if l<>r then begin
                        inc(lazy[k shl 1],v);
                        inc(lazy[k shl 1 or 1],v);
                end;
                exit;
        end;
        m:=(l+r) shr 1;
        updateIT(k shl 1,l,m,i,j,v);
        updateIT(k shl 1 or 1, m+1,r,i,j,v);
        it[k]:=min(it[k shl 1],it[k shl 1 or 1]);
end;

procedure getIT(k,l,r,i,j:longint);
var     m:longint;
begin
        if (l>r) or (r<i) or (j<l) then exit;
        if lazy[k]<>0 then begin
                if l<>r then begin
                        inc(lazy[k shl 1],lazy[k]);
                        inc(lazy[k shl 1 or 1],lazy[k]);
                end;
                inc(it[k],lazy[k]);
                lazy[k]:=0;
        end;
        if (i<=l) and (r<=j) then begin
                res:=min(res,it[k]);
                exit;
        end;
        m:=(l+r) shr 1;
        getIT(k shl 1,l,m,i,j);
        getIT(k shl 1 or 1, m+1,r,i,j);
end;

procedure Enter;
var     i:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n,m);
        readln(inp,s);
        for i:=1 to n do a[i]:=num[s[i]];
        for i:=1 to n do sum[i]:=sum[i-1]+a[i];
        for i:=1 to n do buildIT(1,1,n,i,sum[i]);
        for i:=1 to n do updateBIT(i,a[i]);
end;

begin
        Enter;
        for t:=1 to m do begin
                read(inp,p);
                if p=0 then begin
                        readln(inp,pos,c,c);
                        if a[pos] = num[c] then continue;
                        a[pos]:=num[c];
                        updateBIT(pos,num[c] shl 1);
                        updateIT(1,1,n,pos,n,num[c] shl 1);
                end
                else begin
                        readln(inp,l,r);
                        if not odd(r-l) then begin
                                write(0);
                                continue;
                        end;
                        ok:=0;
                        sl:=getBIT(l-1);
                        sr:=getBIT(r);
                        if sl=sr then begin
                                res:=oo;
                                getIT(1,1,n,l,r);
                                if res>=sl then ok:=1;
                        end;
                        write(ok);
                end;
        end;
end.

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        if (REACHEOF) return 0;\
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 800111;

int n, q;
char a[MN];
int op[MN], cl[MN], bad[MN];

#define CT(x) ((x)<<1)
#define CP(x) (CT(x) + 1)

int match_l;

inline void cal(int i) {
    op[i] = op[CT(i)] + op[CP(i)];
    cl[i] = cl[CT(i)] + cl[CP(i)];

    match_l = min(op[CT(i)], cl[CT(i)] - bad[CT(i)]);

    bad[i] = bad[CT(i)] + max(0, bad[CP(i)] - (op[CT(i)] - match_l));
}

inline void leaf(int i, char c) {
    if (c == '(') {
        op[i] = 1;
        cl[i] = bad[i] = 0;
    }
    else {
        op[i] = 0;
        cl[i] = bad[i] = 1;
    }
}

void init(int i, int l, int r) {
    if (l == r) {
        leaf(i, a[l]);
        return ;
    }
    int mid = (l + r) >> 1;
    init(CT(i), l, mid);
    init(CP(i), mid+1, r);
    cal(i);
}

void update(int i, int l, int r, int u, char c) {
    if (u < l || r < u) return ;
    if (l == r) {
        leaf(i, c);
        return ;
    }
    int mid = (l + r) >> 1;
    update(CT(i), l, mid, u, c);
    update(CP(i), mid+1, r, u, c);
    cal(i);
}

int can;
bool wrong;

void visit(int i, int l, int r, int u, int v) {
    if (v < l || r < u) return ;
    if (u <= l && r <= v) {
        if (bad[i] > can) wrong = true;
        can += op[i] - cl[i];
        return ;
    }
    int mid = (l + r) >> 1;
    visit(CT(i), l, mid, u, v);
    visit(CP(i), mid+1, r, u, v);
}

void solve(int u, int v) {
    can = 0; wrong = false;
    visit(1, 1, n, u, v);
    if (!can && !wrong) putchar('1');
    else putchar('0');
}

int main() {
    scanf("%d%d\n", &n, &q);
    scanf("%s\n", &a[1]);
    init(1,1,n);

    int req, u, v;
    char c;
    while (q--) {
        scanf("%d", &req);
        if (req == 0) {
            scanf("%d %c", &u, &c);
            update(1,1,n,u,c);
        }
        else {
            scanf("%d%d", &u, &v);
            solve(u, v);
        }
    }
    puts("");
    return 0;
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
class SegmentTree {
    private:
        static const int INF=(int)1e9+7;
        vector<int> tree,lazy;
        int n;
        void pushdown(int i) {
            if (lazy[i]==0) return;
            FOR(j,2*i,2*i+1) {
                tree[j]+=lazy[i];
                lazy[j]+=lazy[i];
            }
            lazy[i]=0;
        }
        int getMin(int i,int l,int r,int u,int v,int add) const {
            if (l>v || r<u || l>r || v<u) return (INF);
            if (u<=l && r<=v) return (tree[i]+add);
            int m=(l+r)>>1;
            int L=getMin(2*i,l,m,u,v,add+lazy[i]);
            int R=getMin(2*i+1,m+1,r,u,v,add+lazy[i]);
            return (min(L,R));
        }
        void update(int i,int l,int r,int u,int v,int c) {
            if (l>v || r<u || l>r || v<u) return;
            if (u<=l && r<=v) {
                tree[i]+=c;
                lazy[i]+=c;
                return;
            }
            pushdown(i);
            int m=(l+r)>>1;
            update(2*i,l,m,u,v,c);
            update(2*i+1,m+1,r,u,v,c);
            tree[i]=min(tree[2*i],tree[2*i+1]);
        }
    public:
        SegmentTree() {
            n=0;
        }
        SegmentTree(int n) {
            this->n=n;
            tree.assign(4*n+7,0);
            lazy.assign(4*n+7,0);
        }
        void update(int l,int r,int c) {
            update(1,1,n,l,r,c);
        }
        int getMin(int l,int r) const {
            return (getMin(1,1,n,l,r,0));
        }
};
class FenwickTree {
    private:
        int n;
        vector<int> v;
    public:
        FenwickTree() {
            n=0;
        }
        FenwickTree(int n) {
            this->n=n;
            v.assign(n+7,0);
        }
        void update(int x,int d) {
            if (x<1) return;
            for (;x<=n;x+=x&-x) v[x]+=d;
        }
        int getSum(int x) const {
            int res=0;
            if (x>n) return (0);
            for (;x>=1;x&=x-1) res+=v[x];
            return (res);
        }
};
char s[MAX];
int a[MAX];
int n,q;
SegmentTree myit;
FenwickTree bit;
void init(void) {
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    FOR(i,1,n) a[i]=s[i]=='('?1:-1;
    myit=SegmentTree(n);
    bit=FenwickTree(n);
    FOR(i,1,n) myit.update(i,n,a[i]);
    FOR(i,1,n) bit.update(i,a[i]);
}
void update(int x,int v) {
    if (a[x]==v) return;
    myit.update(x,n,v-a[x]);
    bit.update(x,v-a[x]);
    a[x]=v;
}
bool ok(int l,int r) {
    if ((r-l+1)%2!=0) return (false);
    int prevSum=l==1?0:bit.getSum(l-1);
    if (myit.getMin(l,r)-prevSum<0) return (false);
    return (bit.getSum(r)==prevSum);
}
void process(void) {
    REP(zz,q) {
        int t,l,r;
        char s[2];
        scanf("%d%d",&t,&l);
        if (t==0) {
            scanf("%s",s);
            update(l,s[0]=='('?1:-1);
        } else {
            scanf("%d",&r);
            printf("%d",ok(l,r)?1:0);
        }
    }
}
int main(void) {
    init();
    process();
    return 0;
}