Submission #74678983

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
typedef pair<ll,ll> PII;
typedef array<ll,2> a2;
typedef array<ll,3> a3;
int n,m,k;
int a[N];
bool tf[N];
vector<int> ed;
vector<int> v[N];
map<string,int> mp;

void cal(vector<int> v){
    string s;
    for(auto j:v){
        char ch='a'+j;
        s+=ch;
    }
    for(int i=0;i<s.size();i++){
        string s0;
        for(int j=i;j<s.size();j++){
            s0+=s[j];
            mp[s0]++;
        }
    }
}


struct ExSam
{
	string s ;
	int last , cnt ;
	vector<vector<int>> tr ;
	vector<int> nxt ;
	vector<int> len ;
	void init(int t)
	{
		last = cnt = 1 ;
		int up1 = t * 2 + 10 ;
		int up2 = 30 ; //字符集大小
		tr.resize(0) ; //这是清空
		tr.resize(up1 , vector<int>(up2 , 0)) ; //这是赋值
		nxt.resize(0) ;
		nxt.resize(up1 , 0) ;
		len.resize(0) ;
		len.resize(up1 , 0) ;
	}
	void add(int c)
	{
		if(tr[last][c])
		{
			int p = last , x = tr[p][c] ;
			if(len[p] + 1 == len[x])  
			{
				last = x ;
				return ;//即最初的特判1
			}
			else
			{
				int y = ++ cnt ;
				len[y] = len[p] + 1 ;
				for(int i = 0 ; i < 26 ; i ++)  tr[y][i] = tr[x][i] ;
				while(p && tr[p][c] == x)  tr[p][c] = y , p = nxt[p] ;
				nxt[y] = nxt[x] , nxt[x] = y ;
				last = y ;
				return ;  //即最初的特判2
			}
		}
		int p = last , np = ++ cnt ;
		last = np , len[np] = len[p] + 1 ;
		for( ; p && !tr[p][c] ; p = nxt[p])  tr[p][c] = np ;
		if(!p)  nxt[np] = 1 ;
		else
		{
			int q = tr[p][c] ;
			if(len[p] + 1 == len[q])  nxt[np] = q ;
			else
			{
				int nq = ++ cnt ;
				len[nq] = len[p] + 1 ;
				tr[nq].assign(tr[q].begin() , tr[q].end()) ;
				nxt[nq] = nxt[q] , nxt[q] = nxt[np] = nq ;
				for( ; tr[p][c] == q ; p = nxt[p])  tr[p][c] = nq ;
			}
		}
	}
	void build(const string &s)
	{
		last = 1 ;
		for(auto &u : s)  add(u - 'a') ;
	}
	void cal()
	{
		long long ans = 0 ;
		for(int i = 1 ; i <= cnt ; i ++)  ans += len[i] - len[nxt[i]] ;
		cout << ans << '\n' ;
	}
} exsam ;
void __(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    exsam.init(1000000 + 10) ;
    int i=1,idx=1;
    while(i<=n){
        int j=i,cnt=0;
        while(j<=n&&a[i]==a[j]){
            j++;
            cnt++;
        }
        if(cnt<a[i]){
            idx++;
            i=j;
        }else if(cnt==a[i]){
            v[idx].push_back(a[i]);
            i=j;
        }else{
            v[idx].push_back(a[i]);
            i=j-a[i];
            idx++;
        }
    }
    for(int i=1;i<=idx;i++){
        // cal(v[i]);
        string s;
        if(!v[i].size()) continue;
        for(auto j:v[i]){
            char ch='a'+j-1;
            s+=ch;
        }
        exsam.build(s);
    }
    exsam.cal();
    
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    // cin>>_;
    while(_--){
        __();
    }
}

Submission Info

Compile Error

./Main.cpp: In function 'void cal(std::vector<int>)':
./Main.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~
./Main.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int j=i;j<s.size();j++){
      |                     ~^~~~~~~~~

Judge Result