CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) E. Bracket Cost（思维 括号匹配）

题意：

给你一个括号序列：
对于$\frac{n\ast (n-1)}{2}$种substring，把它们变成合法的括号序列的操作和。（每个子串的操作单独计算

操作：

• 在任意一个位置加 $“(”或者“)”$
• 选择原串的一个子串，之后进行循环移位。

思路：

step0

括号问题，我们一般先转换一下为前缀和

for(int i = 1; i <= n; i ++ ){
	pre[i] = pre[i-1];
	if(s[i] == '(') pre[i]++;
	else pre[i]--;
}
1
2
3
4
5

一个区间$[l,r]$合法
$\rightleftharpoons$
$pre[l-1]==pre[r]$
$\&\&$
$min(pre[l-1],pre[l],...,pre[r])>=pre[r]$

step1:

• 每个子串的贡献：

1. 如果$pre[l-1]<pre[r]$ ，我们可以用操作1，加 “）”
2. 如果$pre[l-1]>pre[r]$,我们可以用操作1，加“（”
3. 如果$pre[l-1]==pre[r]$

yy下，下面的两种情况。

发现 $ans0=max(pre[l-1],pre[r])-min(pre[l-1]...pre[r])$

• 所有子串的贡献：
  发现答案，是两个之差，那么我们分开计算所有子串的情况。
  $res1={\sum }_{l=0}^n{\sum }_{r=l+1}^{n}max(pre[l],pre[r])$
  $res2=-{\sum }_{l=0}^n{\sum }_{r=l+1}^n,min(pre[l],...,pre[r])$

step2:

计算res1.

经典的树状数组，解决逆序对问题

我们通过枚举右端点$r$，

• $pre[r]$作为最大值的贡献，我们可以使用树状数组（就是找$r$以前的有多少$pre[r]\ge$$pre[l]$。
• $pre[l]$作为最大值的贡献 $pre[l]>pre[r]$

step3:

计算res2
使用单调栈，搞下
计算$pre[i]$作为最小值时，找到左边第一个比它小的，右边第一个比它小或者等于它的。（容斥一下

AC

package com.hgs.codeforces.contest.div1div2.CodeTONRound3.e;

/**
 * @author youtsuha
 * @version 1.0
 * Create by 2022/11/6 22:27
 */
import java.util.*;
import java.io.*;
public class Main {
    static FastScanner cin;
    static PrintWriter cout;

    private static void init()throws IOException {
        cin = new FastScanner(System.in);
        cout = new PrintWriter(System.out);
    }

    private static void close(){
        cout.close();
    }
    static int n;
    static long tr1[];
    static long tr2[];
    static int lowbit(int x) { return x&-x; }
    static void add(int x, int v, long tr[]){
        for(int i = x; i < 2*n + 5; i += lowbit(i)) tr[i] += v;
    }
    static long sum(int x, long tr[]){
        long res = 0;
        for(int i = x; i > 0; i -= lowbit(i)) res += tr[i];
        return res;
    }
    private static void sol()throws IOException {
        n = cin.nextInt();
        String s = cin.next();
        int pre[] = new int[n+1];
        for(int i = 1; i <= n; i ++ ) {
            pre[i] = pre[i-1];
            if(s.charAt(i-1) == '(') pre[i]++;
            else pre[i]--;
        }
        /*   res1 */
        long res1 = 0;
        tr1 = new long[2*n+5];//small
        tr2 = new long[2*n+5];//big
        add(pre[0]+n + 1,1, tr1);
        add(pre[0]+n+1, pre[0], tr2);
        for(int i = 1; i <= n; i ++ ) {

            res1 += sum(pre[i]+n + 1, tr1)*1L*pre[i];
            res1 += sum(2*n+1, tr2) - sum(pre[i] + n + 1, tr2);
            add(pre[i] + n + 1, 1, tr1);
            add(pre[i] + n + 1, pre[i], tr2);
        }
        /*  res2  */
        long res2 = 0;
        Stack<Integer> stk = new Stack<>();
        int left[] = new int[n+2];
        int right[] = new int[n+2];

        //stack Left <
        for(int i = 0; i <= n; i ++ ) {
            //1 2 3 2
            while(stk.size() != 0 && pre[stk.peek()] >= pre[i]) stk.pop();
            if(stk.size() == 0) left[i] = -1;
            else left[i] = stk.peek();
            stk.push(i);
        }
        //stack right <=
        stk.clear();
        for(int i = n; i >= 0; i -- ) {
            //1 2 2
            while(stk.size() != 0 && pre[stk.peek()] > pre[i]) stk.pop();
            if(stk.size() == 0) right[i] = n + 1;
            else right[i] = stk.peek();
            stk.push(i);
        }
        for(int i = 1; i <= n; i ++ ) {
            long l = i - left[i];
            long r = right[i] - i;
            res2 += (l*r - 1)*pre[i];
        }
        cout.println(res1-res2);
    }
    public static void main(String[] args) throws IOException {
        init();
        int tt = cin.nextInt();
        while(tt-- > 0)sol();
        close();
    }
}
class FastScanner {
    BufferedReader br;
    StringTokenizer st = new StringTokenizer("");

    public FastScanner(InputStream s) {
        br = new BufferedReader(new InputStreamReader(s));
    }

    public FastScanner(String s) throws FileNotFoundException {
        br = new BufferedReader(new FileReader(new File(s)));
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()){
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) { e.printStackTrace(); }
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126