思路:

给定一个局面，我们约定出现次数最多的牌为x , 它的出现次数为mx

1.小美至少需要将所有的x翻出来，所以最差情况就是mx次

2.特殊情况是：如果除了x以外,其他的都是1种，那么我们最多只需要翻出mx-1次（这mx-1次翻出来的全是x）即可（见官方给的样例）。

3.非法情况:如果mx <= 1，也就是出现次数全是1,则不可能翻出两张相同的牌，也就不可能获胜。

4.维护牌种类的过程使用线段即可。

代码

java

import java.util.Scanner;
class Main {
    static long[] r;
    static long[] mx;
    static int[] idx;
    static int n, q;
    static long[] a;
    static long[] lz;
    static long[] l;
    static void sol() {
        if (n == 1) {
            System.out.println(-1);
            return;
        }
        int ii = get(1, 1, n);
        int i = idx[ii];
        int ma = -1;
        if (i != 1) ma = get(1, 1, i - 1);
        if (i != n) {
            int t = get(1, i + 1, n);
            if (ma == -1 || mx[t] > mx[ma]) ma = t;
        }
        if (mx[ma] == 0 || mx[ii] <= 1) {
            System.out.println(-1);
        } else if (mx[ma] == 1) {
            System.out.println(mx[ii] - 1);
        } else {
            System.out.println(mx[ii]);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        q = sc.nextInt();

        a = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextLong();
        }

        int N = n * 4 + 10;
        lz = new long[N];
        l = new long[N];
        r = new long[N];
        mx = new long[N];
        idx = new int[N];
        build(1, 1, n);
        sol();
        for (int i = 0; i < q; i++) {
            String op = sc.next();
            int left = sc.nextInt();
            int right = sc.nextInt();
            long v = sc.nextLong();
            if (op.equals("-")) {
                v = -v;
            }
            fix(1, left, right, v);
            sol();
        }
        sc.close();
    }

    static int get(int s, int left, int right) {
        if (l[s] >= left && r[s] <= right) {
            return s;
        }
        down(s);
        int res = -1;
        int mid = (int) (l[s] + r[s]) / 2;
        if (left <= mid) res = get(s * 2, left, right);
        if (right > mid) {
            int t = get(s * 2 + 1, left, right);
            if (res == -1 || mx[t] > mx[res]) res = t;
        }
        return res;
    }
    static void up(int s) {
        if (mx[s * 2] >= mx[s * 2 + 1]) {
            mx[s] = mx[s * 2];
            idx[s] = idx[s * 2];
        } else {
            mx[s] = mx[s * 2 + 1];
            idx[s] = idx[s * 2 + 1];
        }
    }

    static void down(int s) {
        lz[s * 2] += lz[s];
        lz[s * 2 + 1] += lz[s];
        mx[s * 2] += lz[s];
        mx[s * 2 + 1] += lz[s];
        lz[s] = 0;
    }

    static void build(int s, int left, int right) {
        l[s] = left;
        r[s] = right;
        if (left == right) {
            mx[s] = a[left];
            idx[s] = left;
            return;
        }
        int mid = (left + right) / 2;
        build(s * 2, left, mid);
        build(s * 2 + 1, mid + 1, right);
        up(s);
    }

    static void fix(int s, int left, int right, long v) {
        if (l[s] >= left && r[s] <= right) {
            mx[s] += v;
            lz[s] += v;
            return;
        }
        down(s);
        int mid = (int) (l[s] + r[s]) / 2;
        if (left <= mid) fix(s * 2, left, right, v);
        if (right > mid) fix(s * 2 + 1, left, right, v);
        up(s);
    }


}
/*

2 1
1 1
+ 2 2 1
*/

python

to be fill

cpp

to be fill

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

小美和小美在玩一个卡牌游戏，初始时桌面上有$n$种卡牌，每种卡牌有$a_i$张，这些牌都是背面朝上的。玩家操作时会先翻一张牌，然后再翻一张牌，若两张牌的类型相同，则玩家获胜，否则，重新将两张票翻回背面朝上，两个玩家轮流操作。

小美和小妹总共会玩$q+1$轮游戏。第$1$轮的卡牌数量为初始数量，后续每一轮会在上一轮游戏的基础上，增加或减少一些卡牌，然后将所有卡牌翻至背面朝上并重新打乱。

增加卡牌的操作为：$+l \ r\ x\$表示第$l$种牌到第$r$种牌各增加$x$张。

增加卡牌的操作为：$-l \ r\ x\$表示第$l$种牌到第$r$种牌各减少$x$张。

每一轮都是由小美先手，小美想让小妹获胜，小美想知道他至少需要偷看多少张牌才能保证小妹一定能获得胜利？若无法保证小美一定获得胜利，则输出$-1$

输入描述

第一行输入$2$个正整数$n,q$($1≤n，q≤10^5$)，表示卡牌种类和游戏轮数。

第$2$行输入$n$个整数$a_i$($0≤a_i≤10^9$)表示数组。

接下来$q$行，每行先输入$1$个字符$c$($c∈${$'-','+'$})，再输入$3$个数字$l,x$($1≤l≤r≤n$)，$x$($1≤x≤10^9$)，表示操作。

数据保证，任意一轮开始前，每种卡牌的数量都为非负整数，且每种卡牌数量之和不小于$2$

输出描述

输出$q+1$行，每行输出一个整数表示答案。

样例1

输入

2 1
1 1
+ 2 2 1

输出

-1
1

说明

第$1$轮，很显然，小美和小美永远都赢不了。

第$2$轮，小美可以偷看$1$张牌，若看到的是第$1$种牌，则翻开这张牌和任意一张其他牌；若看到的是第$2$种牌，则翻开另外两张牌。