题解——[NOIP模拟]不正常全家桶

题解——不正常团伙+国家+序列

体面背景好评
关于ssw02,他炸了


不正常团伙

主要思路

50分做法

开桶暴力,统计即可。

60分做法

主席树加暴力

100分做法

由50分做法可得,莫队离线一下就可以了。(这里顺便借ZYC学长的代码优化了一下ssw02自己的莫队板子)

由60分做法可得,主席树记录上一个位置即可。

线段树做法,也是记录上一个位置。(区间染色也就这几种方法了)

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 100005 ;
inline int read(){
   int s=0 , w=1 ; char g=getchar() ;while(g>'9'||g<'0'){if(g=='-')w=-1;g=getchar();}
   while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ;return w*s ;
}
struct Seg{
   int l , r , id ;
}t[ MAXN ];
int N , M , block , a[ MAXN ] , pos[ MAXN ] , num[ MAXN ]  ;
ll tot = 0 , ans[ MAXN ] ;
inline bool cmp( Seg x , Seg y ){
   return ( pos[ x.l ]==pos[ y.l ] )?( x.r < y.r ) : ( pos[x.l] < pos[y.l] ) ;
}
inline void updata( int x , int  opt ){
   if( !opt ){//收缩 扩张 
       --num[ a[ x ] ] ;
       if( num[ a[ x ] ] > 2 ) tot -= a[ x ];
       else if(num[ a[ x ] ] == 2) tot -= a[ x ]*3 ;  
       else if(num[ a[ x ] ] == 1) tot += a[ x ] ;
       else tot -= a[ x ] ; 
       return;
   }
   ++num[ a[ x ] ] ;
   if( num[ a[ x ] ] > 3 )  tot += a[ x ];
   else if( num[ a[ x ] ] == 3 ) tot += a[ x ]*3 ;
   else if( num[ a[ x ] ] == 2 ) tot -= a[ x ] ;
   else tot += a[ x ];
}
void  Mo(){
   for( int l = 1 , r = 0 , i = 1 ; i <= M  ; ++i ){
       while( l < t[ i ].l )updata( l++ , 0 ) ;
       while( l > t[ i ].l )updata( --l , 1 ) ;
       while( r < t[ i ].r )updata( ++r , 1 ) ;
       while( r > t[ i ].r )updata( r-- , 0 ) ;
       ans[ t[ i ].id ] = tot ;
   }
}
int main(){
   freopen("abnormal.in","r",stdin);
   freopen("abnormal.out","w",stdout);
   N = read() , M = read() , block = sqrt(N) ;
   for( int i = 1 ; i <= N ; ++i )a[ i ] = read() ;
   block = sqrt( N ) ;
   for( int i = 1 ; i <= N ; ++i )pos[ i ] = (i-1) / block+1 ;
   for( int i = 1 ; i <= M ; ++i )
       t[ i ].l = read() , t[ i ].r = read() , t[ i ].id = i ;
   sort( t+1 , t+M+1 , cmp ) ;
   Mo() ;
   for( int i = 1 ; i <= M ; ++i )printf("%lld\n",ans[ i ] ) ;
   return 0 ;
} 

作为一个OIer,要时刻保持对出题人的尊敬,尤其是本校金牌学长出的题。

不正常国家

重链剖分+trie树+启发式合并( SXK , std )
trie树+无删除启发式合并( ZYC )
树剖+trie树+启发式合并(其实和第一种差不多)

不正常序列

毒瘤出题人完美卡了所有平衡树。(最后有hzy卡时莽了过去)

求中位数,用双堆吧。常数小了不止一个级别。

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 1000005 , mod = 1e9+7 ;
inline ll read(){
    ll s=0 ; char g=getchar() ; while(g>'9'||g<'0')g=getchar() ;
    while( g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ;
}
ll ans = 0 ;
ll a[ MAXN ] , N , A , B , C ; 
priority_queue<ll>ma,mi ;
int  deal( int N ){
    if( N%2 )return N/2+1 ;
    else return N/2 ;
}
void  insert( int x ){
    int u = mi.top() ;
    if( x < u )mi.push( x ) ;
    else ma.push( -x ) ;
    while( mi.size() < ma.size() ){
        int u = -ma.top() ; ma.pop() ;
        mi.push( u ) ;
    }
    while( mi.size()-1 > ma.size() ){
        int u = mi.top() ; mi.pop() ;
        ma.push( -u ) ;
    }
}
int main(){
    freopen("unnormal.in","r",stdin) ;
    freopen("unnormal.out","w",stdout) ;
    A = read() , B = read() , C = read() , N = read() ;
    mi.push(1) ;
    ans = 1LL ;
    for( ll i = 2 ; i <= N ; ++i ){
        ll op = mi.top() ;
        op = ( op*A%mod + B*i%mod + C )%mod ; 
        insert(op);ans += (ll)op ;
    }
    cout<<ans<<endl ;
}

如有不足,请大佬指出

上一篇:第23课.神秘的临时对象


下一篇:CodeForces - 1251E2 (思维+贪心)