Java(javac 1.8) 解法, 执行用时: 1104ms, 内存消耗: 75124K, 提交时间: 2019-12-07 23:41:34
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Random;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) throws IOException {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader sc = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
solver.solve(1, sc, out);
out.close();
}
static class Task {
public void solve(int testNumber, InputReader sx, PrintWriter outs) throws IOException {
/* File file_in=new File("C:\\Users\\Garett\\Desktop\\题目\\完美世界\\数据","20.in");
FileReader in=new FileReader(file_in);
BufferedReader sc=new BufferedReader(in);
File file_out=new File("C:\\Users\\Garett\\Desktop\\题目\\完美世界\\数据","20.out");
FileWriter out=new FileWriter(file_out);
BufferedWriter puts=new BufferedWriter(out);
String[] temp=sc.readLine().split(" ");
int n=Integer.parseInt(temp[0]);
int m=Integer.parseInt(temp[1]);
char[] buf=(" "+sc.readLine()).toCharArray();*/
int n=sx.nextInt();
int m=sx.nextInt();
char[] buf=(" "+sx.next()).toCharArray();
int[] cur=new int[buf.length];
for(int i=1;i<buf.length;i++) {
if(buf[i]=='(')
cur[i]=1;
else
cur[i]=0;
}
SegmentTree sgt=new SegmentTree(n,buf);
sgt.build(1, 1, n);
boolean flag=false;
while(m-->0) {
/*temp=sc.readLine().split(" ");
char opt=temp[0].charAt(0);
int l=Integer.parseInt(temp[1]);
int r=Integer.parseInt(temp[2]);*/
char opt=sx.next().charAt(0);
int l=sx.nextInt();
int r=sx.nextInt();
if(opt=='c') {
cur[l]^=1;
cur[r]^=1;
sgt.change(1, l);
sgt.change(1, r);
if(sgt.t[1].l_val==0&&sgt.t[1].r_val==0) {
// puts.println("YES");
outs.println("YES");
flag=true;
}
else
//puts.println("NO");
outs.println("NO");
}
if(opt=='q') {
SegmentTree.Node ans=sgt.ask(1, l, r);
if(ans.l_val==0&&ans.r_val==0) {
//puts.println("YES");
outs.println("YES");
flag=true;
}
else
//puts.println("NO");
outs.println("NO");
}
if(opt=='t') {
int temp=cur[l];
cur[l]=cur[r];
cur[r]=temp;
sgt.change(1, l ,cur[l]);
sgt.change(1, r ,cur[r]);
if(sgt.t[1].l_val==0&&sgt.t[1].r_val==0) {
// puts.println("YES");
outs.println("YES");
flag=true;
}
else
//puts.println("NO");
outs.println("NO");
}
// puts.newLine();
}
/*System.out.println(flag);
puts.close();
sc.close();*/
}
}
public static class SegmentTree{
class Node{
int l;
int r;
int l_val;
int r_val;
public Node(int l,int r) {
this.l=l;
this.r=r;
}
public Node(int l,int r,int l_val,int r_val) {
this.l=l;
this.r=r;
this.l_val=l_val;
this.r_val=r_val;
}
}
public char[] buf;
public Node[] t;
public SegmentTree(int n,char[] buf) {
this.buf=buf;
this.t=new Node[(n+10)<<2];
}
public void pushUp(int p) {
int temp1=t[p*2].l_val;
int temp2=t[p*2+1].r_val;
t[p].l_val=Math.max(0, temp1-temp2)+t[p*2+1].l_val;
t[p].r_val=t[p*2].r_val+Math.max(0, temp2-temp1);
}
public void build(int p,int l,int r) {
t[p]=new Node(l,r);
if(l==r) {
if(buf[l]=='(')
t[p].l_val=1;
else
t[p].r_val=1;
return ;
}
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
pushUp(p);
}
public void change(int p,int index,int val) { //1置为左括号 0置为括号
if(t[p].l==t[p].r) {
if(val==1) {
t[p].l_val=1;
t[p].r_val=0;
}
else {
t[p].l_val=0;
t[p].r_val=1;
}
return ;
}
int mid=(t[p].l+t[p].r)>>1;
if(index<=mid)
change(p*2,index,val);
else
change(p*2+1,index,val);
pushUp(p);
}
public void change(int p,int index) {
if(t[p].l==t[p].r) {
if(t[p].l_val==1) {
t[p].l_val=0;
t[p].r_val=1;
}
else {
t[p].l_val=1;
t[p].r_val=0;
}
return ;
}
int mid=(t[p].l+t[p].r)>>1;
if(index<=mid)
change(p*2,index);
else
change(p*2+1,index);
pushUp(p);
}
public Node ask(int p,int l,int r) {
if(t[p].l>=l&&t[p].r<=r)
return t[p];
Node res1=null;
Node res2=null;
int mid=(t[p].l+t[p].r)>>1;
if(l<=mid)
res1=ask(p*2,l,r);
if(r>mid)
res2=ask(p*2+1,l,r);
if(res1==null)
return res2;
if(res2==null)
return res1;
int temp1=res1.l_val;
int temp2=res2.r_val;
int l_val=Math.max(0, temp1-temp2)+res2.l_val;
int r_val=res1.r_val+Math.max(0, temp2-temp1);
return new Node(0,0,l_val,r_val);
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
C++14(g++5.4) 解法, 执行用时: 267ms, 内存消耗: 5372K, 提交时间: 2020-02-05 21:05:05
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 7;
typedef long long ll;
struct node {
int l, r, val;
int lazy;
}t[maxn*4];
int val[maxn];
void pushup(int n) {
t[n].val = min(t[n<<1].val, t[n<<1|1].val);
}
void pushdown(int n) {
if(t[n].lazy) {
int l = t[n].l, r = t[n].r;
if(l == r) return;
int mid = (l + r)>> 1;
t[n<<1].val += t[n].lazy;
t[n<<1|1].val += t[n].lazy;
t[n<<1].lazy += t[n].lazy;
t[n<<1|1].lazy += t[n].lazy;
t[n].lazy = 0;
}
}
void build(int n, int l, int r) {
t[n].l = l;
t[n].r = r;
t[n].lazy = 0;
if(l == r) {
t[n].val = val[l];
return;
}
int mid = (l + r) >> 1;
build(n<<1, l, mid);
build(n<<1|1, mid + 1, r);
pushup(n);
}
void update(int n, int L, int R, int C) {
int l = t[n].l, r = t[n].r;
if(L <= l && R >= r) {
t[n].lazy += C;
t[n].val += C;
return;
}
pushdown(n);
int mid = (l + r) >> 1;
if(L <= mid) update(n<<1, L, R, C);
if(R > mid) update(n<<1|1, L, R, C);
pushup(n);
}
int query(int n, int L, int R) {
if(L == 0 && R == 0) return 0;
int l = t[n].l, r = t[n].r;
if(L <= l && R >= r) {
return t[n].val;
}
pushdown(n);
int mid = (l + r) >> 1, ans = INF;
if(L <= mid) ans = min(ans, query(n<<1, L, R));
if(R > mid) ans = min(ans, query(n<<1|1, L, R));
return ans;
}
int cal(int x, int y) {
int tmp = query(1, x - 1, x - 1);
int sum = query(1, y, y) - tmp;
update(1, x, y, -tmp);
int minx = query(1, x, y);
if(minx == 0 && sum == 0) printf("YES\n");
else printf("NO\n");
update(1, x, y, tmp);
}
int main()
{
int n, m;
cin >> n >> m;
char s[maxn];
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) {
if(s[i] == '(') val[i] = val[i - 1] + 1;
else val[i] = val[i - 1] - 1;
}
build(1, 1, n);
while (m--) {
char ss[100];
int x, y;
scanf("%s %d %d", ss, &x, &y);
if(ss[0] == 't') {
if(s[x] == '(' && s[y] == ')') {
update(1, x, y - 1, -2);
s[y] = '(';
s[x] = ')';
}
else if(s[x] == ')' && s[y] == '(') {
update(1, x, y - 1, 2);
s[x] = '('; s[y] = ')';
}
cal(1, n);
}
else if(ss[0] == 'c') {
if(s[x] == ')') update(1, x, n, 2), s[x] = '(';
else update(1, x, n, -2), s[x] = ')';
if(s[y] == '(') update(1, y, n, -2), s[y] = ')';
else update(1, y, n, 2), s[y] = '(';
cal(1, n);
}
else if(ss[0] == 'q') {
cal(x, y);
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 157ms, 内存消耗: 4588K, 提交时间: 2019-12-07 23:41:10
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define inf 0x3f3f3f3f
#define ll long long
#define ull unsigned long long
#define inff 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=1e5+5;
int n,m;
char s[N];
int val[N],a[N<<2],lz[N<<2];
void build(int l,int r,int alt)//建树
{
if(l==r){
a[alt]=val[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,alt<<1);
build(mid+1,r,alt<<1|1);
a[alt]=max(a[alt<<1],a[alt<<1|1]);
}
void pushDown(int alt)//向下更新
{
if(lz[alt]){
a[alt<<1]+=lz[alt];
lz[alt<<1]+=lz[alt];
a[alt<<1|1]+=lz[alt];
lz[alt<<1|1]+=lz[alt];
lz[alt]=0;
}
}
void update(int l,int r,int alt,int L,int R,int k)//区间更新
{
if(L<=l&&r<=R){
a[alt]+=k;lz[alt]+=k;
return ;
}
pushDown(alt);
int mid=(l+r)>>1;
if(L<=mid) update(l,mid,alt<<1,L,R,k);
if(R>mid) update(mid+1,r,alt<<1|1,L,R,k);
a[alt]=max(a[alt<<1],a[alt<<1|1]);
}
int queryRange(int l,int r,int alt,int L,int R)//区间查询
{
if(L<=l&&r<=R){
return a[alt];
}
pushDown(alt);
int mid=(l+r)>>1,mi=-inf;
if(L<=mid) mi=max(mi,queryRange(l,mid,alt<<1,L,R));
if(R>mid) mi=max(mi,queryRange(mid+1,r,alt<<1|1,L,R));
return mi;
}
int queryPoint(int l,int r,int alt,int x)//单点查询
{
if(x==0) return 0;
if(l==r){
return a[alt];
}
pushDown(alt);
int mid=(l+r)>>1;
if(x<=mid) return queryPoint(l,mid,alt<<1,x);
else return queryPoint(mid+1,r,alt<<1|1,x);
}
void solve(int l,int r)//判断该区间是否完全匹配
{
int ect=queryPoint(1,n,1,l-1);
int sum=queryPoint(1,n,1,r)-ect;
update(1,n,1,l,r,-ect);//区间-a[l-1],再找最小值
int mi=queryRange(1,n,1,l,r);
if(mi<=0&&sum==0) puts("YES");
else puts("NO");
update(1,n,1,l,r,ect);//区间还原+a[l-1]
}
int main()
{
scanf("%d%d",&n,&m);
scanf("%s",s+1);
for(int i=1;i<=n;i++){
if(s[i]=='(') val[i]=val[i-1]-1;
else val[i]=val[i-1]+1;
}
build(1,n,1);
while(m--){
char c;int l,r;getchar();
scanf("%c %d %d",&c,&l,&r);
if(c=='c'){
if(s[l]=='(') update(1,n,1,l,n,2),s[l]=')';
else update(1,n,1,l,n,-2),s[l]='(';
if(s[r]=='(') update(1,n,1,r,n,2),s[r]=')';
else update(1,n,1,r,n,-2),s[r]='(';
solve(1,n);
}else if(c=='q'){
solve(l,r);
}else if(c=='t'){
//情况一
if(s[l]=='('&&s[r]==')') update(1,n,1,l,r-1,2);
//情况二
else if(s[l]==')'&&s[r]=='(') update(1,n,1,l,r-1,-2);
swap(s[l],s[r]);
solve(1,n);
}
}
return 0;
}
,
,
{ 'c','q','t' } ）