1006

签到 ZRC 记忆化搜索（可直接模拟

1003

签到 LYF 猜结论

1007

“rnm 退钱”

签到 构造 ZRC&LYF

没啥好说的，出题人欺负我英语不好，样例给的还是1呜呜呜

下次看到这种不明不白的样例就得觉得有坑

补1009

题意：

问1e6的数列中，存在 出现频率大于一半的众数的区间数有多少个。值域1e6

解：

先讲一讲赛场上的思路吧

首先因为数据范围很大，就感觉像是O(n)题。同时可以想到一个O(n)的做法Boyer-Moore 投票算法。但是不知道怎么用上去。

曾经碰到过一些随机选择位置统计概率的题，显然这里要求的是准确的区间数，而不是判定性问题，没法做。

那就从暴力开始思考：

  1. O(n)枚举起始位置，做n遍Moore投票算法，途中记录每个数的出现次数，每次查询投票算法中的当前数是否出现次数大于一半。总复杂度$O(n^2)$
  2. 设一共出现了k种数，遍历每一种数，每一次把这种数看成+1，其它数看成-1，对它跑一遍$O(n\lg n)$的扫描。权值线段树或树状数组可以解决。总复杂度$O(kn\lg n)$
  3. 分块，对出现次数小于$\sqrt{n}$的和大于的分别处理。比赛时没有细想，因为铁定过不了。题解说这样复杂度是$O(n^\frac{3}{2}\lg n+n^\frac{3}{2})$的，可以通过调整块大小将两者均摊到$O(n^{\frac{3}{2}}\sqrt{\lg n})$
  4. 类似2的做法，拿权值线段树来维护前缀和。统计答案时统计有多少位置的前缀和比当前位置小。但是这样处理难以统计右端点不在+1上的答案，暴力统计的话复杂度又会和方法2一样
  5. 类似4的做法，用树套树维护，还没想清楚是否真的能做，但超高的复杂度$O(n\lg^2n)$和更高的代码难度让人望而却步

于是就gg了

首先考虑方法4的直接优化：

定义$a[x]$的含义为 值为$x$的位置有$a[x]$个。则对$a[x]$的区间加等价于对其差分数组$c[x]$的单点修改。同时定义$a[x]$的前缀和数组为$s[x]$，$s[x]$的前缀和数组为$g[x]$

将-1看成一段一段的连续段，则这其中产生的答案应当等于$s[x]$的区间和，等价于为$g[x]$的单点求值问题。

一段-1产生的修改为对$a[x]$的区间加，即对$c[x]$的单点加。

考虑魔改树状数组(类似区间树状数组的模式)，使其得以查询$c[x]$的前缀和的前缀和的前缀和

首先树状数组自己就能解决一维，毕竟本来树状数组就是拿来搞前缀和的
$$
g[n]=\sum _ {m=1} ^ n a[m]\cdot \frac{(2+n-m)(n-m+1)}{2}\\
=\frac{(n+1)(n+2)}{2}\sum _ {m=1} ^ n a[m]-\frac{1}{2}\sum _ {m=1} ^ n 2nm\cdot a[m]+\frac{1}{2} \sum _ {m=1} ^ n m^2\cdot a[m]-\frac{1}{2}\sum _ {m=1} ^ n 3m\cdot a[m]\\
=\frac{(n+1)(n+2)}{2}\sum _ {m=1} ^ n a[m]+\frac{1}{2} \sum _ {m=1} ^ n m^2\cdot a[m]-\frac{1}{2}\sum _ {m=1} ^ n (2n+3)m\cdot a[m]
$$
维护三个树状数组即可。

考虑方法4的利用题目性质的优化：

可以发现一共最多只有$O(n)$个-1位置作为右端点时会产生答案(考试时候主要就是没想到这个)。只需要维护区间加和区间和，容易在线段树上维护。然而卡常。

能过的正解主要是两种：

  1. 用区间树状数组维护上面的方法4
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
//by Richard
#include <bits/stdc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
using namespace std;
mt19937 rnd(19260817);
const int inf=0x3f3f3f3f;
typedef long long LL;
typedef pair<int,int> pii;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=1000011;
struct interval_BIT
{
    struct BIT
	{
        LL c[maxn<<1];
        void cg(int x,LL v){while (x<=maxn<<1) {c[x]+=v;x+=lowbit(x);}}
        LL qr(LL x){LL res=0;while (x){res+=c[x];x-=lowbit(x);}return res;}
    }b,c;
    void change(int l,int r,int v){l+=1000001,r+=1000001;b.cg(l,v);b.cg(r+1,-v);c.cg(l,v*l);c.cg(r+1,-v*(r+1));}
    LL query(int l,int r)
	{
        l+=1000001,r+=1000001;
        LL suml=(LL)l*b.qr(l-1)-c.qr(l-1);
        LL sumr=(LL)(r+1)*b.qr(r)-c.qr(r);
        return sumr-suml;
    }
}ibit;
int T,n,a[maxn];
vector<int> pos[maxn];
int main()
{
    read(T);
    while (T--)
    {
        read(n);
        rep(i,1,n) read(a[i]);
        rep(i,1,n) pos[a[i]].push_back(i);
        LL ans=0;
        rep(c,0,1000000)
        {
            if (pos[c].empty()) continue;
            int lastpos=0,lastsum=0,minsum=0;//last sum after adding
            for (auto to:pos[c])
            {
                int nowsum=lastsum;
                rep(i,lastpos,to-1) 
                {
                    ans+=ibit.query(-1000000,nowsum-1);
                    nowsum--;
                    if (nowsum<minsum)
                    {
                        minsum=nowsum;
                        break;
                    }
                }
                int newsum=lastpos==0?(-to+1):(lastsum-(to-lastpos-1));//sum now before adding
                minsum=min(newsum,minsum);
                ibit.change(newsum,lastsum,1);
                lastsum=newsum+1;
                lastpos=to;
            }
            int nowsum=lastsum;
            rep(i,lastpos,n) 
            {
                ans+=ibit.query(-1000000,nowsum-1);
                nowsum--;
                if (nowsum<minsum)
                {
                    minsum=nowsum;
                    break;
                }
            }
            lastsum=0,lastpos=0;
            for (auto to:pos[c])
            {
                int newsum=lastpos==0?(-to+1):(lastsum-(to-lastpos-1));//sum now before adding
                ibit.change(newsum,lastsum,-1);
                lastsum=newsum+1;
                lastpos=to;
            }
        }
        printf("%lld\n",ans);
        rep(i,1,n) pos[a[i]].clear();
    }
    return 0;
}

  1. 差分+前缀和。正解1可以被优化。具体看std吧（有了上面的树状数组做法其实很显然）
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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define pb push_back
const int maxn=2222222;
vector<int>G[maxn];//出现位置
int main()
{
    int n,t;
    cin>>t;
    while (t--)
    {
        cin>>n;
        unordered_set<int>s;//存在哪些数
        vector<int>a(n+1);
        rep(i,1,n)
        {
            cin>>a[i];
            s.insert(a[i]);
            G[a[i]].pb(i);
        }
        LL ans=0;
        for (auto num:s) // 枚举每个数作为众数
        {
            LL res=0;// 答案
            LL sum=0;// 当前前缀和
            unordered_map<int,int>f1,f2;// 前缀和为sum的点有f1[sum]个
            G[num].pb(n+1);//把没处理完的统计进答案
            LL k=0,minn=0;
            rep(j,1,n)
            {
                if (j>G[num][k]) k++;
                if (a[j]!=num&&sum==minn)
                {
                    LL len=G[num][k]-j-1;
                    f2[sum+1]--;
                    f2[sum-len]++;
                    j+=len;
                    sum-=len+1;
                }
                else if (a[j]==num)
                {
                    f1[sum]+=f2[sum];
                    f2[sum+1]+=f2[sum];
                    f2[sum]=0;
                    f1[sum]++;
                    res+=f1[sum];
                    sum++;
                    ans+=res;
                }
                else
                {
                    f1[sum]++;
                    sum--;
                    res-=f1[sum];
                    ans+=res;
                }
                if (minn>sum) minn=sum;
            }
        }
        cout<<ans<<endl;
        for (auto &i:s) G[i].clear();
    }
    return 0;
}