文章目錄

• T1：單峰排列
• • 題目
  • 題解
  • code
• T2：歷史研究
• • 題目
  • 題解
  • code
• T3：大魔法師
• • 題目
  • 題解
  • code

我可能這輩子都更不出來狂歡賽5了，先咕咕

T1：單峰排列

題目

一個n的全排列A[i]是單峰的，當且僅當存在某個x使得A[1]<A[2]<…<A[x]>A[x+1]>…> A[n]
例如，對于9的全排列，125798643是一個單峰排列，123456789也是一個單峰排列，但356298741就不是
試求n的單峰全排列的個數(shù)

輸入格式
輸入一個數(shù)n
輸出格式
輸出n的全排列中單峰排列的個數(shù)。
由于這個數(shù)可能很大，因此你只需要輸出它mod 1234567的值。

樣例
輸入樣例:
3
輸出樣例:
4
樣例說明 共有以下4種方案： 123 132 231 321
數(shù)據(jù)范圍與提示
n<=2 000 000 000

題解

暴力打表找到規(guī)律$2^{n?1}$

簡單證明一下：
我們把最大值即最高峰固定后，剩下的$n?1$個數(shù)會有兩種選法，在最大值左邊或右邊$2^{n?1}$
理論上還要乘以一個階乘，但是我們發(fā)現(xiàn)要成為單峰的話，同在最大值左邊的數(shù)相對位置是固定的，是不能進行亂排的，證畢！！

code

#include <cstdio> #define mod 1234567 #define LL long long int n; LL qkpow ( LL x, LL y ) {LL ans = 1;while ( y ) {if ( y & 1 )ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; } int main() {scanf ( "%d", &n );LL ans = qkpow ( 2, n - 1 );printf ( "%lld", ans % mod );return 0; }

T2：歷史研究

題目

IOI國歷史研究的第一人——JOI教授，最近獲得了一份被認為是古代IOI國的住民寫下的日記。JOI教授為了通過這份日記來研究古代IOI國的生活，開始著手調(diào)查日記中記載的事件。

日記中記錄了連續(xù)N天發(fā)生的時間，大約每天發(fā)生一件
事件有種類之分,第i天(1<=i<=N)發(fā)生的事件的種類用一個整數(shù)$X_i$表示，$X_i$ 越大，事件的規(guī)模就越大。

JOIJOI教授決定用如下的方法分析這些日記：
選擇日記中連續(xù)的一些天作為分析的時間段
事件種類t的重要度為t*(這段時間內(nèi)重要度為t的事件數(shù))
計算出所有事件種類的重要度，輸出其中的最大值 現(xiàn)在你被要求制作一個幫助教授分析的程序，每次給出分析的區(qū)間，你需要輸出重要度的最大值。

輸入輸出格式
輸入格式
第一行兩個空格分隔的整數(shù)N和Q，表示日記一共記錄了N天，詢問有Q次
接下來一行N個空格分隔的整數(shù)$X_1...X_N$表示第i天發(fā)生的事件的種類
接下來Q行，第i行(1<=i<=Q)有兩個空格分隔整數(shù)$A_i$ 和$B_i$表示第i次詢問的區(qū)間為$[A_i,B_i]$

輸出格式
輸出Q行，第i行(1<=i<=Q)一個整數(shù)，表示第i次詢問的最大重要度

輸入輸出樣例
輸入：
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
輸出：
9
8
8
16
16
數(shù)據(jù)范圍
$1<=N<=10^5,1<=Q<=10^5,1<=X_i<=10^9(1<=i<=N)$

題解

這道題首先肯定能反應(yīng)是莫隊，但是答案告訴你$T$了，所以我們要學(xué)習一個新的回滾莫隊

假設(shè)要查詢$[l,r]$區(qū)間，按照平時我們要移動$curl,curr$，但是我們轉(zhuǎn)變想法對于$l$同在一個分塊的查詢，每一次都把$curl$回撥到這一區(qū)域的最后處然后移動到$l$

但是這張圖是錯的，你看出來了嗎？因為同在一個塊的操作$r$一定是遞增的，所以上圖中的第二根紅線應(yīng)該在最后一個豎黑線的右邊

具體操作細節(jié)在code中有體現(xiàn)

code

#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define LL long long #define maxn 100005 struct node {int l, r, id; }query[maxn]; int n, q, T; int block[maxn]; LL result; LL a[maxn], val[maxn], cnt[maxn], tot[maxn], ans[maxn]; bool cmp ( node x, node y ) {//以塊為第一關(guān)鍵字，右端點為第二關(guān)鍵字 return block[x.l] == block[y.l] ? x.r < y.r : block[x.l] < block[y.l]; }void add ( int x ) {cnt[a[x]] ++;result = max ( result, cnt[a[x]] * val[a[x]] );//當規(guī)模為i的時間多了一件，重要度就多了i } void remove ( int x ) {cnt[a[x]] --; }int main() {scanf ( "%d %d", &n, &q );T = sqrt ( n );for ( int i = 1;i <= n;i ++ ) {scanf ( "%lld", &a[i] );block[i] = ( i - 1 ) / T + 1;val[i] = a[i];}int num = block[n];//離散化，1e9最多只會變成1e5，但是規(guī)模在計算時要用原來的，所以不能直接替代 sort ( val + 1, val + n + 1 );int len = unique ( val + 1, val + n + 1 ) - val - 1;for ( int i = 1;i <= n;i ++ )a[i] = lower_bound ( val + 1, val + len + 1, a[i] ) - val; for ( int i = 1;i <= q;i ++ ) {scanf ( "%d %d", &query[i].l, &query[i].r );query[i].id = i;}sort ( query + 1, query + q + 1, cmp );int i = 1;//已經(jīng)處理到哪一個query操作了 for ( int id = 1;id <= num;id ++ ) {//依次處理每一塊int tail = min ( n, id * T );//有可能塊數(shù)乘以大小反而炸了n int curl = tail + 1, curr = tail;result = 0;memset ( cnt, 0, sizeof ( cnt ) );//每一個塊都重新開始，與其他塊無瓜for ( ;block[query[i].l] == id;i ++ ) {//屬于同一塊的每個操作一定是右端點遞增的 int l = query[i].l, r = query[i].r;if ( block[query[i].l] == block[query[i].r] ) {//整一個詢問都在該塊中，暴力求解 LL sum = 0;//不能用result，該次詢問根本沒用到塊以外的元素 for ( int k = l;k <= r;k ++ )tot[a[k]] = 0;//注意不是對tot[k]清零 for ( int k = l;k <= r;k ++ ) {tot[a[k]] ++;sum = max ( sum, tot[a[k]] * val[a[k]] );}ans[query[i].id] = sum;continue;}while ( curr < r )add ( ++ curr );//curr貢獻已經(jīng)算過，所以先加后算，curl同理 LL tmp = result;//r一定是遞增的，記錄下此時塊的末尾到n的ans，方便下面的還原 while ( curl > l )add ( -- curl );ans[query[i].id] = result;while ( curl <= tail )//把curl撥回到下一個塊的開頭，表示沒有一個元素，等到下一次移動到新的l remove ( curl ++ );result = tmp;//重置起始值}}for ( int i = 1;i <= q;i ++ )printf ( "%lld\n", ans[i] );return 0; }

T3：大魔法師

題目

中二病患者 大魔法師小 L 制作了$n$個魔力水晶球，每個水晶球有水、火、土三個屬性的能量值。小 L 把這 個水晶球在地上從前向后排成一行，然后開始今天的魔法表演。

我們用$A_i,B_i,C_i$分別表示從前向后第$i$個水晶球（下標從 開始）的水、火、土的能量值。

小 L 計劃施展$m$次魔法。每次，他會選擇一個區(qū)間$[l,r]$，然后施展以下3大類、7種魔法之一：

魔力激發(fā)：令區(qū)間里每個水晶球中特定屬性的能量爆發(fā)，從而使另一個特定屬性的能量增強。具體來說，有以下三種可能的表現(xiàn)形式：
火元素激發(fā)水元素能量：令$A_i=A_i+B_i$ 。
土元素激發(fā)火元素能量：令$B_i=B_i+C_i$ 。
水元素激發(fā)土元素能量：令$C_i=C_i+A_i$ 。
需要注意的是，增強一種屬性的能量并不會改變另一種屬性的能量，例如$A_i=A_i+B_i$并不會使$B_i$增加或減少。

魔力增強：小 L 揮舞法杖，消耗自身$v$點法力值，來改變區(qū)間里每個水晶球的特定屬性的能量。具體來說，有以下三種可能的表現(xiàn)形式：

火元素能量定值增強：令$A_i=A_i+v$。
水元素能量翻倍增強：令$B_i=B_i?v$ 。
土元素能量吸收融合：令$C_i=v$ 。
魔力釋放：小L將區(qū)間里所有水晶球的能量聚集在一起，融合成一個新的水晶球，然后送給場外觀眾。生成的水晶球每種屬性的能量值等于區(qū)間內(nèi)所有水晶球?qū)?yīng)能量值的代數(shù)和。需要注意的是，魔力釋放的過程不會真正改變區(qū)間內(nèi)水晶球的能量。

值得一提的是，小 L 制造和融合的水晶球的原材料都是定制版的 OI 工廠水晶，所以這些水晶球有一個能量閾值$998244353$ 。當水晶球中某種屬性的能量值大于等于這個閾值時，能量值會自動對閾值取模，從而避免水晶球爆炸。

小 W 為小 L（唯一的）觀眾，圍觀了整個表演，并且收到了小 L 在表演中融合的每個水晶球。小 W 想知道，這些水晶球蘊涵的三種屬性的能量值分別是多少

題解

首先大家都能想到線段樹，我當時直接暴力線段樹開搞，后來操作時寫崩了，這個更改太給力
況且因為有懶標記的介入，$a,b,c$都會改了后再彼此影響，我們根本不知道先后順序
那咱不用懶標記唄

那么怎么能將懶標記按順序疊加呢？矩陣！！！

對于操作1，即乘上
$$?\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 0& 0& 1\end{array}?$$
操作2，乘上
$$?\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 1\end{array}?$$
操作3，乘上
$$?\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 0& 0& 1\end{array}?$$
操作4，我們發(fā)現(xiàn)怎么加常數(shù)？多給矩陣開一位（上面就不再次多余重復(fù)），乘上
$$?\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ v& 0& 0& 1\end{array}?$$
操作5，乘上
$$?\begin{array}{cccc}1& 0& 0& 0\\ 0& v& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}?$$
操作6，乘上
$$?\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 0& v& 1\end{array}?$$

---

然后矩陣的懶標記就可以直接疊加了，最后送大家五句忠告

1、此做法常數(shù)大，寫的不好看會100–>45
2、矩陣從0開始，別從1，某朋友MLE
3、矩陣逼著4開，多開1，親測TLE
4、longlong比int取模會慢一倍，所以你懂的
5、取模本身也很慢，能不取模就不取模

code

#include <cstdio> #include <cstring> #define maxn 250005 const int mod = 998244353; struct Matrix {int c[4][4]; //開成c[5][5]就T了一個點，因為我們每次都用了memset，多清了一行，浪費時間 Matrix () {memset ( c, 0, sizeof ( c ) );} }unit, ret, A[maxn], tag[maxn << 2], tree[maxn << 2]; //unit是單位矩陣 void read ( int &x ) {x = 0;char s = getchar();while ( s < '0' || s > '9' )s = getchar();while ( '0' <= s && s <= '9' ) {x = ( x << 1 ) + ( x << 3 ) + ( s - '0' );s = getchar();} }int add ( int x, int y ) {x = 1ll * x + y;return x >= mod ? x - mod : x; }Matrix operator + ( Matrix x, Matrix y ) {Matrix ans;for ( int i = 0;i < 4;i ++ )ans.c[0][i] = add ( x.c[0][i], y.c[0][i] );return ans; }void build ( int t, int l, int r ) {tag[t] = unit;if ( l == r ) {tree[t] = A[l];return;}int mid = ( l + r ) >> 1;build ( t << 1, l, mid );build ( t << 1 | 1, mid + 1, r );tree[t] = tree[t << 1] + tree[t << 1 | 1]; }void MakeMark ( int t, Matrix f ) {Matrix ans;for ( int i = 0;i < 4;i ++ )for ( int j = 0;j < 4;j ++ )if ( f.c[i][j] )ans.c[0][j] = add ( ans.c[0][j], 1ll * tree[t].c[0][i] * f.c[i][j] % mod );tree[t] = ans;ans = Matrix();for ( int i = 0;i < 4;i ++ )for ( int j = 0;j < 4;j ++ )if ( tag[t].c[i][j] ) //稀疏矩陣優(yōu)化 for ( int k = 0;k < 4;k ++ )if ( f.c[j][k] )ans.c[i][k] = add ( ans.c[i][k], 1ll * tag[t].c[i][j] * f.c[j][k] % mod );tag[t] = ans; }void pushdown ( int t ) {MakeMark ( t << 1, tag[t] );MakeMark ( t << 1 | 1, tag[t] );tag[t] = unit;//注意清除標記就是變成單位矩陣不是0 }void modify ( int t, int l, int r, int L, int R, Matrix f ) {if ( L <= l && r <= R ) {MakeMark ( t, f );return;}int mid = ( l + r ) >> 1;pushdown ( t );if ( L <= mid )modify ( t << 1, l, mid, L, R, f );if ( mid < R )modify ( t << 1 | 1, mid + 1, r, L, R, f );tree[t] = tree[t << 1] + tree[t << 1 | 1]; }Matrix query ( int t, int l, int r, int L, int R ) {if ( L <= l && r <= R )return tree[t];pushdown ( t );int mid = ( l + r ) >> 1;if ( R <= mid )return query ( t << 1, l, mid, L, R );else if ( mid < L )return query ( t << 1 | 1, mid + 1, r, L, R );elsereturn query ( t << 1, l, mid, L, R ) + query ( t << 1 | 1, mid + 1, r, L, R ); }int main() {int n, m;read ( n );for ( int i = 1;i <= n;i ++ ) {for ( int j = 0;j < 3;j ++ )read ( A[i].c[0][j] );A[i].c[0][3] = 1;}for( int i = 0;i < 4;i ++ )unit.c[i][i] = 1;build ( 1, 1, n );read ( m );int opt, l, r, v;for ( int i = 1;i <= m;i ++ ) {read ( opt );read ( l );read ( r );if ( 4 <= opt && opt <= 6 )read ( v );if ( opt == 7 ) {Matrix ans = query ( 1, 1, n, l, r );printf ( "%d %d %d\n", ans.c[0][0], ans.c[0][1], ans.c[0][2] );continue;}ret = unit;//重置成單位矩陣再進行修改操作 switch ( opt ) {case 1 : ret.c[1][0] = 1;break;case 2 : ret.c[2][1] = 1;break;case 3 : ret.c[0][2] = 1;break;case 4 : ret.c[3][0] = v;break;case 5 : ret.c[1][1] = v;break;case 6 : ret.c[2][2] = 0, ret.c[3][2] = v;break;}modify ( 1, 1, n, l, r, ret );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【周末狂欢赛6】[AT1219]历史研究(回滚莫队)，大魔法师(矩阵+线段树)，单峰排列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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