Location>code7788 >text

20241120 Intramural Mock T3 Problem Solving

Popularity：99 ℃/2024-11-20 10:01:39

Title Description

Given a sequence of numbers\(A\)The range of values of the elements of the series is\([1,m]\)。

Calculate how many non-empty subintervals satisfy the condition that each element in the interval has the same number of occurrences (elements that do not occur are considered to occur)\(0\) (Times).

For example, when\(m=3\) when\([1,2,3]\) cap (a poem)\([1,1,3,2,3,2]\) is an interval that satisfies the condition, and\([1,2,2,3]\) cap (a poem)\([1,1,3,3]\) The conditions are not met.

Calculate the series\(A\) of the number of nonempty subintervals that satisfy the condition.

input format

Contains multiple sets of test data, first row a positive integer\(T\) Represents the number of data sets.

Two rows for each data set, two integers in the first row\(n,m\), representing the sequence length and element value field.

second line\(n\) An integer, representing the sequence, ensures that the elements of the sequence are in the\([1,m]\) Between.

output format

\(T\) rows, one integer per row, representing the number of satisfying non-empty subintervals of the sequence corresponding to the group number data.

example

Sample Input 1

1
6 3
1 2 3 1 2 3

Sample Output 1

5

Sample explanation 1

there are\([1,3],[2,4],[3,5],[4,6],[1,6]\) common\(55\) Individuals.

Sample Input 2

1
10 4
1 1 2 4 3 2 4 3 2 1

Sample Output 2

3

Sample explanation 2

there are\([2,5],[1,8],[7,10]\) common\(33\) Individuals.

Data ranges and tips

insofar as\(100%\) of the data.\(1≤T≤5,1≤n≤106,1≤m≤n\)。

test point \(n\) \(m\)
\(1\) \(≤50\) \(≤50\)
\(2\) \(≤300\) \(≤300\)
\(3\) \(≤3000\) \(≤3000\)
\(4\) \(≤7000\) \(≤7000\)
\(5,6,7\) \(≤7 × 10^4\) \(≤300\)
\(8\) \(≤3×10^5\) \(≤3×10^5\)
\(9,10\) \(≤10^6\) \(≤10^6\)

Description of the solution

Let us first consider the practice of violence. Remember\(f_{i,j}\) For the period up to\(i\) terminology\(j\) occurrences, it is clear that for the interval\((l,r]\), if and only if\(\forall i,j \in [1,m],f_{r,i}-f_{l,i}=f_{r,j}-f_{l,j}\) The interval is legal at the time.

Next consider optimization. This is in fact equivalent to the optimization of\(f_i\) cap (a poem)\(f_j\) look forincrementarrays, when the two difference arraysequalwhen the interval is legal. At this point the original problem is transformed into maintaining each position\(f\) of the set of difference arrays to find the number of matches. The number of matches can be found using a method similar tohashThe trick to find each position\(f\) of the hash of the difference array to quickly find the answer. This complexity is good enough to get full marks.

But from the abovehashperspective, there is a simpler way to do this. UseMersenne Spingenerating\(m-1\) numbers, respectively, as\(A_1\) until (a time)\(A_{m-1}\) The hash value of thethe opposite of andbecause of\(A_m\) The hash value of the The hash value of the hash value of the\(id_i\) indicate\(i\) The hash value of the hash, notated\(f_i=\sum_{j=1}^i id_{A_j}\)，When all numbers have the same number of occurrences, the sum of their hash values should be\(0\)The i.e.For intervals\((l,r]\), if and only if\(f_l=f_r\) The interval is legal whenThe therefore\(f\) The logarithm of the same element in is the answer to the original question.

By Code

#include<bits/stdc++.h>

#define int long long// Remember to turn on long long
#define ull unsigned long long
const int N=1e6+10;

namespace IO{
    inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<||ch>|'0'||ch>|'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch <='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f; }
    inline void write(int x){ if(x>9) write(x/10); putchar(x%10+'0'); }
}using namespace IO;//fast read and write

namespace code{
    int n,m,ans,id[N].
    ull a[N],sum;
    std::mt19937_64 random(time(0));//generate high-quality pseudo-random number sequences using the Mersenne rotation algorithm

    void solve(){
        n=read(),m=read(),ans=0,sum=0;//multiple tests are not cleared, loved ones two lines of tears
        for(int i=1;i<m;++i) id[i]=random(),sum+=id[i];//for the first 1 to m-1 items assigned hash value
        id[m]=-sum;//the hash value of the mth item is the hash value of the first m-1 items and the opposite of the sum of hash values
        for(int i=1;i<=n;++i) a[i]=a[i-1]+id[read()];//a[i] denotes the sum of the hashes of items 1 to i
        std::sort(a,a+n+1);//sort for easy computation
        for(int i=1,cnt=1;i<=n;++i,++cnt,ans+=cnt-1) if(a[i]! =a[i-1]) cnt=0;//accumulate answers
        write(ans),putchar('\n');
    }
}

signed main(){
    freopen("", "r",stdin); freopen("", "w",stdin); }
    freopen("", "w",stdout);//don't forget file manipulation
    int T=read();
    while(T--) code::solve();
    return 0;
}
<Previous Next>