今天热身考到FFT,完全忘光了,模板敲错了。。。 晚上温习下以前的题目
这题就是从最大值每次分割现在的区间,这样递归的区间最大值会更小,对于每种最大值都是卷积做
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 60005; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int n; int a[MAXN]; ll cnt[MAXN]; vector<int> po[MAXN]; // x的所有位置 /*********Segtree************/ int tree[MAXN<<2]; void Build(int l,int r,int rt){ if(l == r) { tree[rt] = a[l]; return; } int m = (l+r)>>1; Build(lson); Build(rson); tree[rt] = max(tree[rt<<1], tree[rt<<1|1]); } int Query(int L,int R,int l,int r,int rt){ if(L <= l && r <= R) return tree[rt]; int m = (l+r)>>1; int ans = -1; if(L <= m) ans = max(ans, Query(L,R,lson) ); if(R > m) ans = max(ans, Query(L,R,rson) ); return ans; } /***************FFT**********/ int A[MAXN<<2], B[MAXN<<2]; int C[MAXN<<2]; namespace FFT { int pos[MAXN<<2]; struct comp { double r , i ; comp ( double _r = 0 , double _i = 0 ) : r ( _r ) , i ( _i ) {} comp operator + ( const comp& x ) { return comp ( r + x.r , i + x.i ) ; } comp operator - ( const comp& x ) { return comp ( r - x.r , i - x.i ) ; } comp operator * ( const comp& x ) { return comp ( r * x.r - i * x.i , i * x.r + r * x.i ) ; } comp conj () { return comp ( r , -i ) ; } } A[MAXN<<2] , B[MAXN<<2] ; const double pi = acos ( -1.0 ) ; void FFT ( comp a[] , int n , int t ) { for ( int i = 1 ; i < n ; ++ i ) if ( pos[i] > i ) swap ( a[i] , a[pos[i]] ) ; for ( int d = 0 ; ( 1 << d ) < n ; ++ d ) { int m = 1 << d , m2 = m << 1 ; double o = pi * 2 / m2 * t ; comp _w ( cos ( o ) , sin ( o ) ) ; for ( int i = 0 ; i < n ; i += m2 ) { comp w ( 1 , 0 ) ; for ( int j = 0 ; j < m ; ++ j ) { comp& A = a[i + j + m] , &B = a[i + j] , t = w * A ; A = B - t ; B = B + t ; w = w * _w ; } } } if ( t == -1 ) for ( int i = 0 ; i < n ; ++ i ) a[i].r /= n ; } void mul ( int *a , int *b , int *c ,int k) { int i , j ; for ( i = 0 ; i < k ; ++ i ) A[i] = comp ( a[i] , b[i] ) ; j = __builtin_ctz ( k ) - 1 ; for ( int i = 0 ; i < k ; ++ i ) { pos[i] = pos[i >> 1] >> 1 | ( ( i & 1 ) << j ) ; } FFT ( A , k , 1 ) ; for ( int i = 0 ; i < k ; ++ i ) { j = ( k - i ) & ( k - 1 ) ; B[i] = ( A[i] * A[i] - ( A[j] * A[j] ).conj () ) * comp ( 0 , -0.25 ) ; } FFT ( B , k , -1 ) ; for ( int i = 0 ; i < k ; ++ i ) { c[i] = ( long long ) ( B[i].r + 0.5 ) ; } } } /**************cdq***********/ void cdq(int l,int r){ if(l > r) return; if(l == r) { cnt[1]++; return; } int num = Query(l,r,1,n,1); int st = lower_bound(po[num].begin(), po[num].end(), l) - po[num].begin(); int ed = upper_bound(po[num].begin(), po[num].end(), r) - po[num].begin()-1; int m = 0; for(int i = st; i <= ed+1; ++i){ int le = st==i? l-1 : po[num][i-1]; int re = ed+1==i? r+1 : po[num][i]; A[m++] = re-le; } int len = 1; while(len < 2*m) len<<=1; for(int i = 0; i < m; ++i) B[i] = A[m-1-i]; for(int i = m; i < len; ++i) A[i]=0, B[i]=0; FFT::mul(A,B,C,len); for(int i = 0; i < m; ++i){ cnt[i+1] += C[i+m]; } for(int i = st; i <= ed+1; ++i){ int le = st==i? l-1 : po[num][i-1]; int re = ed+1==i? r+1 : po[num][i]; cdq(le+1, re-1); } } int main(){ int T; scanf("%d",&T); while(T--){ scanf("%d",&n); memset(cnt,0,sizeof(cnt)); for(int i = 1; i <= n; ++i) po[i].clear(); for(int i = 1; i <= n; ++i){ scanf("%d",&a[i]); po[a[i]].push_back(i); } Build(1,n,1); cdq(1,n); ll ans = 0; for(int i = 1; i <= n; ++i) ans += cnt[i]^i; printf("%lld\n",ans); } return 0; }转载于:https://www.cnblogs.com/Basasuya/p/8433724.html
相关资源:垃圾分类数据集及代码