题解——不正常团伙+国家+序列
体面背景好评
*关于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
",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 ;
}