noip模拟赛34
$$
给定 1 \ldots N的一个排列 a ，M 次操作，操作有两种:1 l m r表示将al,al+1,...,ar改为merge(\{a_l,a_{l+1},...,a_m\},\{a_{m+1},a_{m+2},...,a_r\ 2 i ，表示询问 a_i的值是多少。其中 \operatorname{merge}(a, b)表示归并操作，其伪代码如下：[]
$$
~~~
def merge(a, b):
c=[]
while a.size() and b.size():
if a[0]<b[0]:
c. append(a[0])
a.pop_ front()
else:
c. append(b[0])
b.pop_ front()
return c+a+b
~~~
考虑一个平衡树做法，我们把变化的1区间split出来然后旋转一下维护平衡树的性质然后insert回去
QWQ：
$$
维护一个长度为 nn 的数列 a_i，共有 mm 个操作，这些操作共有两种。
]
\\
1 l r k 将区间 [l,r] 内的元素全部修改为 k
\\
2 {l r c} 查询区间内是否存在出现次数大于 c 的数，如果存在，输出 laffey，否则输出 ayanami。
$$
区间推平很明显，是ODT(Old Driver Tree)
具体操作大概就是用set维护好多的桶
经典 set<node > : : iterator
~~~
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
#define FASTIO
#define IOSIZE 100000
char ibuf[IOSIZE], obuf[IOSIZE];
char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#ifdef ONLINE_JUDGE
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif//fread in OJ, stdio in local
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read()
{
T s = 0; int w = 1; char ch;
while(ch=getchar(),!isdigit(ch)and(ch!=EOF)) if(ch=='-') w=-1;
if(ch == EOF) return false;
while(isdigit(ch)) s=s*10+ch-48,ch=getchar();
return s*w;
}
template<typename T> inline bool read(T &s)
{
s = 0; int w = 1; char ch;
while(ch=getchar(),!isdigit(ch)and(ch!=EOF)) if(ch=='-') w=-1;
if(ch == EOF) return false;
while(isdigit(ch)) s=s*10+ch-48,ch=getchar();
return s*=w, true;
}
inline bool read(char &s)
{
while(s = getchar(), isspace(s));
return true;
}
inline bool read(char *s)
{
char ch;
while(ch=getchar(),isspace(ch));
if(ch == EOF) return false;
while(!isspace(ch)) *s++ = ch, ch = getchar();
*s = '\000'; return true;
}
template<typename T> inline void print(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x > 9) print(x/10);
putchar(x%10+48);
}
inline void print(char x){ putchar(x); }
inline void print(char *x){ while(*x) putchar(*x++); }
inline void print(const char *x)
{ for(int i = 0; x[i]; i++) putchar(x[i]); }
#ifdef _GLIBCXX_STRING
inline bool read(std::string& s)
{
s = ""; char ch;
while(ch=getchar(),isspace(ch));
if(ch == EOF) return false;
while(!isspace(ch)) s += ch, ch = getchar();
return true;
}
inline void print(std::string x)
{
for(int i = 0, n = x.size(); i < n; i++)
putchar(x[i]);
}
#endif//string
template<typename T, typename... T1> inline int read(T& a, T1&... other){ return read(a)+read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other){ print(a); print(other...); }
struct Fast_IO{
~Fast_IO(){ fwrite(obuf, p3-obuf, 1, stdout); }
}io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b){ return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b){ return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
}
using namespace fast_IO;
#define ll long long
const int MAXN = 1e6 ;
ll a[MAXN] ;
struct node{
int l ;
int r ;
mutable int v ;
node(ll l , ll r = 0 , ll v = 0) : l(l) , r(r) , v(v) {}
bool operator < (const node &a) const{
return l < a.l ;
}
};
set<node> s ;
set<node>::iterator split(int pos)
{
set<node>::iterator it = s.lower_bound(node(pos)) ;
if(it != s.end() && it -> l == pos) return it ;
it -- ;
if(it -> r < pos) return s.end() ;
ll l = it -> l ;
ll r = it -> r ;
ll v = it -> v ;
s.erase(it) ;
s.insert(node(l,pos-1,v)) ;
return s.insert(node(pos,r,v)).first ;
}
inline void assign(ll l , ll r ,ll x)
{
set<node>::iterator itr = split(r + 1) , itl = split(l) ;
s.erase(itl,itr) ;
s.insert(node(l,r,x)) ;
}
int G[MAXN];
inline bool calc(ll l , ll r , ll x)
{
set<node>::iterator itr = split(r+1) , itl = split(l) ;
bool flag = 1 ;
for(set<node>::iterator it = itl ; it != itr ; it ++ )
{
int g = it->v ;
G[g] += (it -> r - it -> l + 1) ;
if(G[g] > x) flag = 0 ;
}
for(set<node>::iterator it = itl ; it != itr ; it ++ )
{
int g = it->v ;
G[g] -= (it -> r - it -> l + 1) ;
}
return flag ;
}
/*
6
1 1 4 5 1 4
4
2 1 5 2
2 1 6 3
1 5 6 1
2 1 6 3
lal
*/
ll m , n ;
int main()
{
cin >> n ;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> a[i] ;
s.insert(node(i,i,a[i])) ;
}
cin >> m ;
for(int i = 1 ; i <= m ; i ++ )
{
int opt ; int l , r ; int x ;
cin >> opt ;
cin >> l >> r >> x;
if(opt == 1)
{
assign(l , r , x) ;
}
else
{
bool flag = calc(l , r , x) ;
if(flag == false) cout << "laffey" ;
else cout << "ayanami" ;
cout << endl ;
}
}
}
~~~
Problem B: Cigar Box
$$
你有一个序列 \{1,2,3,\cdots,n\}，你可以对它进行以下操作 mm 次：
删除任意一个数，将它加到这个序列的开头或末尾。
最后你需要得到序列 \{a_i\}，这里 a_i是个 1\sim n1∼n 的排列。求合法的方案数模 998244353
两种操作方案相同当且仅当每次操作都选择了相同的元素，移动到了相同的方向。
$$
首先我们不妨先假设我们已经得到了一个操作序列。
因此，我们可以定义对某一个元素的最后一次移动，我们称它为该元素的关键操作。
我们不妨假设我们已经对某两个元素完成了关键操作。
则在当前序列中不在这两个元素之间的元素不能够成为这两个元素之间的元素，换句话说这两个元素间的元素若在目标序列中也在这两个元素之间则他们必然已经完成了他们的关键操作，或者他们完全不用操作。
因此我们得到了结论一：完成关键操作的元素在目标序列中是连续的。
我们考虑那些完全不用操作的元素可能在哪些位置。
我们不妨考虑第一个完成向左的关键操作的元素，则在目标序列中在该元素左边的元素必然需要操作。
第一个完成向右的关键操作的元素同理。
则最后我们发现在第一个完成向左的关键操作的元素和第一个向右的之间的元素是不用操作的。则在目标序列中，这些元素相对位置和原序列中一样，即这些元素单调递增。
我们不妨枚举目标序列中间的一段元素单调递增的区间，由性质一可以得到区间左边这些元素发生关键操作顺序和右边发生关键操作顺序，因此我们可以采用 dp 处理。
定义 dpi,l,r 表示进行 i 个操作后，在目标序列所选定的区间左边的元素中还有 l 个没有发生关键操作，右边还有 r 个没有发生关键操作。
则有转移方程：
dpi+1,l,r+=dpi,l,r×2×(l+r)dpi+1,l−1,r+=dpi,l,rdpi+1,l,r−1+=dpi,l,r
答案是 dpm,0,0。
于是我们得到了 O(n3×m) 的优秀做法。
我们发现我们每次 dp 的转移类似，我们考虑一次性 dp 预处理出所以可能用到的值。
因此类似的，我们可以定义 dpi,l,r 在目标序列所选定的区间左边的元素中还有 l 个没有发生关键操作，右边还有 r 个没有发生关键操作的一种序列变成 ， 在 i 次内变成目标序列的方案数。
这次我们考虑倒序还原。
我们考虑当前的情况是如何得到的，考虑正序时这一步不是任何一个元素的关键操作，则得到这样一个情况我们上一步有 (l+r)×2 个选择。
若正序时这一步是关键操作，则正序时这一步到当前只有唯一一种方式。
则有方程：
dpi+1,l,r=dpi,l,r×2×(l+r)dpi,l+1,r=dpi,l,rdpi,l,r+1=dpi,l,r
对于这个方程我们可以理解为上一个序列是已经确定的，当前这一序列是不确定的，但无论当前长什么样，推到目标序列步数都是一样的，所以不影响。
于是我们得到了 O(n2m+n2) 的优秀算法。
考虑继续优化，我们发现第二个转移方程和第三个相似，我们不妨将后两维其压缩得到 fi,l+r 。转移类似，我们考虑但是实际上， f 计算值是只考虑了发生关键操作与否的顺序，而没有考虑左右关键操作的顺序，因此需要额外计算，于是有 dpi,l,r=fi,l+r×C(l+r,l) 。
~~~
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 3e3+10 ;
const ll mod = 998244353 ;
ll n , m ;
ll a[MAXN],f[MAXN][MAXN],C[MAXN][MAXN];
int main()
{
cin >> n >> m ;
for(ll i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
f[m][0] = 1 ;
for(ll i = m - 1 ; ~i ; i -- )
{
for(ll j = 0 ; j <= n ; j ++ )
{
f[i][j] = 2 * f[i+1][j] * j % mod ;
if(j) f[i][j] = (f[i][j] + f[i+1][j-1]) % mod ;
}
}
for(ll i = 0 ; i <= n ; i ++ )
{
C[i][0] = 1 ;
for(ll j = 1 ; j <= i ; j ++ )
{
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod ;
}
}
ll ans = 0 ;
for(ll i = 0 ; i <= n ; i ++ )
{
ans = (ans + C[n][i] * f[0][n]) % mod ;
}
for(ll i = 1 ; i <= n ; i ++ )
{
ans = (ans + C[n-1][i-1] * f[0][n-1]) % mod ;
for(ll j = i + 1 ; j <= n ; j ++ )
{
if(a[j] < a[j-1]) break ;
ans = (ans + C[n-(j-i+1)][i-1] * f[0][n-(j-i+1)]) % mod ;
}
}
cout << ans ;
return 0 ;
}
~~~
C。wine Thief
$$
给你一个长为 nn 的序列 (a_1,a_2,\cdots,a_n
一种“成功”的子序列 a_{p_1},a_{p_2},\cdots,a_{p_m}
满足下面两个条件：
这个子序列的长度为 K（输入给出）即 m=K
在原序列中没有连续 D（本题 D=2）个元素同时在子序列中，不存在 p_i+1=p_{i+1}
定义一个“成功”子序列的权值为 \sum a_{p_i}”子序列的权值和 \bmod 998244353
$$
Solution:
我们先考虑n个数里选k个数的方案数f(n,k) = C(n-k+1,k) ;
然后我们考虑环上的在链上是$a_1,a_n$可以选但环上不行所以把$a_1,a_n$刨出去=F(n,k) = f(n - 3, k - 1);
然后我们算一个G(n,k,i)表示n个数选k个不连续且必须选I的方案数
if(i <= 0) return 0 ;
if(i == 1) return F(n,k) + f(n-4,k-2) ;
if(i > 1) rrturn F(n,k) + G(n-4,k-2,i-2) ;
if(i > n / 2) G(n,k,n-i+1)
740422015
~~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 7;
ll farc[maxn], inv[maxn];
const int mod = 998244353;
ll qpow(ll a, ll b = mod - 2)
{
ll ans = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1)
ans = ans * a % mod;
return ans;
}
void prework(int n = 3e5)
{
farc[0] = 1;
for (int i = 1; i <= n; i++)
farc[i] = farc[i - 1] * i % mod;
inv[n] = qpow(farc[n]);
inv[0] = 1;
for (int i = n - 1; i >= 1; i--)
inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(int n, int m)
{
if (m > n || m < 0)
return 0;
return farc[n] * inv[m] % mod * inv[n - m] % mod;
}
ll f(ll n, ll k)
{
return C(n - k + 1, k);
}
ll F(ll n, ll k)
{
if (n < 3)
return k == 1;
else
return f(n - 3, k - 1);
}
ll sf[maxn];
ll G(ll n, ll k, ll i)
{
if (i > ceil((double)n / 2.0))
return G(n, k, n - i + 1);
if (i <= 0)
return 0;
if (i == 1)
return (F(n, k) + f(n - 4, k - 2)) % mod;
return (sf[i >> 1] + G(n - ((i >> 1) << 2), k - ((i >> 1) << 1), i & 1)) % mod;
}
int n, k, d;
ll a[maxn];
int main()
{
prework();
cin >> n >> k >> d;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
sf[i] = (sf[i - 1] + F(n - ((i - 1) << 2), k - ((i - 1) << 1))) % mod;
}
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ans += G(n, k, i) * a[i] % mod;
ans %= mod;
}
cout << ans;
return 0;
}
~~~