文章目錄

• 逆序?qū)?/li>
• 對(duì)序列
• 未曾設(shè)想的道路

牛客IOI周賽26-提高組

逆序?qū)?/h1>

這種套路之前已經(jīng)見(jiàn)過(guò)幾次了，肯定不是模擬操作數(shù)列

• opt 1

  對(duì)于$i\in [1,l)?(r,n]$ 逆序?qū)κ遣挥绊懙?/p>

  對(duì)于$i\in (l,r)$ 與$l/r$的情況會(huì)反轉(zhuǎn)，之前是逆序?qū)σ院蟊悴皇?#xff0c;反之同理

  逆序?qū)Φ母淖兦闆r為$2$（偶數(shù)）所以奇偶不變

  因此整個(gè)序列的逆序?qū)ζ媾家驗(yàn)?span id="ze8trgl8bvbq" class="katex--inline">$l,r$的互換一定發(fā)生改變

  （ps: $l=r$）

• opt 2

  反轉(zhuǎn)區(qū)間$[l,r]$

  對(duì)于$i\in [1,l)?(r,n]$ 同樣不影響

  操作區(qū)間的總配對(duì)個(gè)數(shù)$cnt=\frac{len\times (len?1)}{2}$，假設(shè)原區(qū)間逆序?qū)€(gè)數(shù)為$x$，則反轉(zhuǎn)后為$cnt?x$

  發(fā)現(xiàn)最后的奇偶取決于$cnt$的奇（奇加偶）偶（奇加奇/偶加偶）

• opt 3/4

  左移右移本質(zhì)上是一樣的，以左移為例

  將整個(gè)操作區(qū)間重新離散化

  對(duì)于區(qū)間的開(kāi)頭假設(shè)離散化結(jié)果為$x$，意味著原來(lái)該開(kāi)頭的逆序?qū)ω暙I(xiàn)為$x?1$

  左移到最后，就會(huì)與前面的$n?x$個(gè)數(shù)產(chǎn)生逆序?qū)?/p>

  一次移動(dòng)改變數(shù)為$x?1+n?x=?2x+n?1$

  發(fā)現(xiàn)$x$的貢獻(xiàn)因?yàn)閹Я?span id="ze8trgl8bvbq" class="katex--inline">$?2$一定是偶數(shù)，不改變奇偶，無(wú)用直接不管

  所以最后只取決于$k\times (n?1)$的奇偶性

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 200005 int n, m; int a[maxn], tree[maxn], tmp[maxn];int lowbit( int x ) {return x & ( -x ); }void Add( int x ) {for( int i = x;i <= n;i += lowbit( i ) )tree[i] ++; }int Ask( int x ) {int ans = 0;for( int i = x;i;i -= lowbit( i ) )ans += tree[i];return ans; }int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ )scanf( "%d", &a[i] );int ans = 0;for( int i = n;i;i -- )ans += Ask( a[i] ), Add( a[i] );ans = ans & 1;while( m -- ) {int opt, l, r, k;scanf( "%d %d %d", &opt, &l, &r );switch( opt ) {case 1 : {if( l != r ) ans ^= 1;break;}case 2 : {int len = ( r - l + 1 ) * ( r - l ) / 2;if( len & 1 ) ans ^= 1;break;}case 3 : {scanf( "%d", &k );int len = r - l + 1;if( ( k * ( len + 1 ) ) & 1 ) ans ^= 1;break;}case 4 : {scanf( "%d", &k );int len = r - l + 1;if( ( k * ( len - 1 ) ) & 1 ) ans ^= 1;break;}}printf( "%d\n", ans );}return 0; }

對(duì)序列

序列合法的必要條件為：對(duì)于$x$，第二次出現(xiàn)位置后面所有值都不能比$x$小

考慮反過(guò)來(lái)，剩下$n$個(gè)格子，最大能填$m$

$f_{n,m}=f_{n,m?1}+{\sum }_{i=1}^n{f}_{n?i,m?1}\times (n?i+1)$

$f_{n,m?1}:$ 不填$m$的方案數(shù)

$f_{n,m}=f_{n,m?1}+{\sum }_{i=1}^n{f}_{n?i,m?1}\times (n?i+1)$

$?f_{n,m}=f_{n,m?1}+{\sum }_{i=0}^{n?1}{f}_{i,m?1}\times (i+1)$

$g_{n,m}={\sum }_{i=0}^{n?1}{f}_{i,m}\times (i+1)?g_{n,m}=g_{n?1,m}+f_{n?1,m}\times n$

前綴和優(yōu)化

#include <cstdio> #define mod 998244353 #define int long long #define maxn 1005 int f[maxn], g[maxn]; int n, m;signed main() {scanf( "%lld %lld", &n, &m );f[0] = 1;for( int i = 1;i <= n;i ++ )g[i] = ( g[i - 1] + f[i - 1] * i % mod ) % mod;for( int j = 1;j <= m;j ++ )for( int i = 1;i <= n;i ++ ) {f[i] = ( f[i] + g[i] ) % mod;g[i] = ( g[i - 1] + f[i - 1] * i % mod ) % mod;}printf( "%lld\n", f[n] );return 0; }

未曾設(shè)想的道路

維護(hù)連續(xù)的懶標(biāo)記，前$k$大的懶標(biāo)記，現(xiàn)在前$k$大，歷史前$k$大

無(wú)腦樹(shù)套樹(shù)

代碼是正確的，卡卡常就能過(guò)了

#pragma GCC optimize(2) #include <queue> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define inf -1e9 #define maxn 100005 #define maxk 101 #define lson num << 1 #define rson num << 1 | 1 #define Pair pair < int, int > struct node {int lazy;int tag[maxk], maxx[maxk], now[maxk];node() {for( int i = 1;i < maxk;i ++ )tag[i] = maxx[i] = now[i] = inf;} }t[maxn << 2]; priority_queue < Pair > q; int n, m; int h[maxn], tmp[maxk], ans[maxk]; //tag:[1,k]max lazy till now //maxx:[1,k]max Height up till now //now:[1,k]max Height at the present void merge( int *A, int *B ) {static int MS[maxk];int i = 1, j = 1;for( int k = 1;k < maxk;k ++ )if( A[i] > B[j] ) MS[k] = A[i ++];else MS[k] = B[j ++];memcpy( A, MS, sizeof( MS ) ); }void pushup( int num ) {memcpy( t[num].now, t[lson].now, sizeof( t[lson].now ) );merge( t[num].now, t[rson].now );memcpy( t[num].maxx, t[lson].maxx, sizeof( t[lson].maxx ) );merge( t[num].maxx, t[rson].maxx ); }void build( int num, int l, int r ) {if( l == r ) {t[num].maxx[1] = t[num].now[1] = h[l];return; }int mid = ( l + r ) >> 1;build( lson, l, mid );build( rson, mid + 1, r );pushup( num ); }void unite( int *A, int *B ) {static int MS[maxk];while( ! q.empty() ) q.pop();for( int i = 1;i < maxk;i ++ )q.push( make_pair( A[i] + B[1], i ) ), MS[i] = 1;for( int i = 1;i < maxk;i ++ ) {Pair now = q.top(); q.pop();tmp[i] = max( (int)inf, now.first );q.push( make_pair( A[now.second] + B[++ MS[now.second]], now.second ) );} }void pushdown( int num ) {if( t[num].tag[1] > -1e8 ) {for( int i = 1;i < maxk;i ++ )tmp[i] = t[lson].lazy + t[num].tag[i];merge( t[lson].tag, tmp );for( int i = 1;i < maxk;i ++ )tmp[i] = t[rson].lazy + t[num].tag[i];merge( t[rson].tag, tmp );t[lson].lazy += t[num].lazy;t[rson].lazy += t[num].lazy;unite( t[num].tag, t[lson].now );merge( t[lson].maxx, tmp );unite( t[num].tag, t[rson].now );merge( t[rson].maxx, tmp );for( int i = 1;i < maxk;i ++ ) {t[lson].now[i] += t[num].lazy;t[rson].now[i] += t[num].lazy;}for( int i = 1;i < maxk;i ++ )t[num].tag[i] = inf;t[num].lazy = 0;} }void modify( int num, int l, int r, int L, int R, int x ) {if( r < L || R < l ) return;if( L <= l && r <= R ) {t[num].lazy += x;for( int i = 1;i < maxk;i ++ ) tmp[i] = inf; tmp[1] = t[num].lazy;for( int i = 1;i < maxk;i ++ ) t[num].now[i] += x;merge( t[num].tag, tmp );merge( t[num].maxx, t[num].now );return;}pushdown( num );int mid = ( l + r ) >> 1;modify( lson, l, mid, L, R, x );modify( rson, mid + 1, r, L, R, x );pushup( num ); }void query( int num, int l, int r, int L, int R ) {if( R < l || r < L ) return;if( L <= l && r <= R ) {merge( ans, t[num].maxx );return;}int mid = ( l + r ) >> 1;pushdown( num );query( lson, l, mid, L, R );query( rson, mid + 1, r, L, R ); }int main() {scanf( "%d %d", &n, &m );for( int i = 1;i <= n;i ++ )scanf( "%d", &h[i] );build( 1, 1, n );int opt, l, r, k;while( m -- ) {scanf( "%d %d %d %d", &opt, &l, &r, &k );if( ! opt ) modify( 1, 1, n, l, r, k );else {for( int i = 1;i < maxk;i ++ ) ans[i] = inf;query( 1, 1, n, l, r );int ret;for( int i = 1;i <= k;i ++ )if( ans[i] > -1e8 ) ret = ans[i];printf( "%d\n", ret );}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的牛客IOI周赛26-提高组（逆序对，对序列，未曾设想的道路） 题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。