Substrings 第37届ACM/ICPC 杭州赛区现场赛C题(hdu 4455) - JAVA

既然要计算所有贡献和，对于区间长度为k，假设集合中的元素全都相同，那么这个元素将会贡献给所有长度为k 的子区间。而事实上，所有元素不可能相同，因此就不可能贡献给所有长度为k 的子区间，那么思考，那些子区间是无法贡献的。假设集合中有序列 1......1，如果两个1的间隔为s，那么对于(k

而且，只要是任意的k

s1-k

s2-k

。。。 sum-k*cnt，记录s 的和，记录s>k的个数，就可以求出没法贡献的次数。再用总数减去就行了。有点抽象，能理解的理解理解。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
               #include
               
                 using namespace std; #define FOR(i,a,b) for(int i=a;i
                
                 b;i--) #define MST(a,num) memset(a,num,sizeof(a)) #define MCP(d,s) memcpy(d,s,sizeof(s)) #define WH(n) while(scanf(%d, &n) != EOF) #define WHZ(n) while(scanf(%d, &n) != EOF && n != 0) #define SCF(a) scanf(%d,&a) #define PRF(a) printf(%d,a) #define PRS(a) printf(%s,a) #define PRFF(a) printf(%d ,a) #define PRSF(a) printf(%s ,a) #define PRFFU(a) printf(%I64d ,a) #define PI acos(-1) #define max3(a,b,c) max(max(a,b),c) #define max4(a,b,c,d) max(max(a,b),max(c,d)) #define FORE(e,x) for(__typeof(x.begin()) e=x.begin(); e!=x.end(); e++) //foreach(it, ans ) cout<<*it<< ; #define all(a) (a).begin(),(a).end() //sort(all(v)); #define len(a) ((int)(a).size()) #define pb push_back #define mk make_pair #define V(etype) vector
                 
                   typedef __int64 Uint; typedef vector
                  
                    Vint; typedef pair
                   
                    mypair; #define INF 0x3f3f3f3f #define eps 1e-9 #define N 1000000+10 int q[N]; int head[N]; int rt[N]; int cnt[N]; int num[N]; Uint sum[N]; int main() { int n,a,m; // freopen(data.in,r,stdin); // freopen(data2.out,w,stdout); while((cin>>n)&&n){ MST(cnt,0); MST(sum,0); MST(rt,-1); MST(head,-1); q[0]=0; FOR(i,0,n){ SCF(num[i]); if(head[num[i]]==-1)q[++q[0]]=num[i]; rt[i]=head[num[i]]; head[num[i]]=i; } FOR(i,1,q[0]+1){ rt[n]=head[q[i]]; for(int j=n;j!=-1;j=rt[j]){ cnt[j-rt[j]]--; sum[j-rt[j]]-=j-rt[j]; cnt[0]++; sum[0]+=j-rt[j]; } } FOR(i,1,n){ sum[i]+=sum[i-1],cnt[i]+=cnt[i-1]; //ret[i]=(n-i+1)*q[0]-(sum[i]-num[i]*cnt[i]); } Uint s1,s2; SCF(m); while(m--){ SCF(a); if(!a)PRSF(0 ); else{ s1=(n-a+1); s1*=q[0]; s2=a; s2*=cnt[a]; s2=sum[a]-s2; PRFFU(s1-s2); } } } return 0; } /* 7 1 1 2 3 4 4 5 3 1 2 3 7 1 1 2 3 4 4 5 4 1 2 3 0 */