tokitsukaze and Unlimited Array

牛客的题

真的不想去修latex了,,将就看一下吧

题解

自我感觉写得很啰嗦QAQ

Step one

原多项式是F(x) 最终要求的是差分n+1次后数组的和。

因为差分n+1次得到的前无穷项的和,就是差分n次后的第无穷项。

定义多项式F(x)的差分操作。一个多项式差分后还是一个多项式。具体而言,F(x)差分后是\Delta F(x),那么\Delta F(x) = F(x) - F(x-1)

当然,这个差分和题目里面的不一样。题目中差分后第一项还是第一项。这个的确会造成影响。但是,对于第n次差分这只影响前n-1项。当我们求出了进行n阶差分后的函数f(x)后,只需要求出f(\infin)

也就是说,到此为止我们已经成功把问题转化成了多项式的差分

Step two

接着说明一下一个n次多项式F(x),差分n次后一定是一个常量函数。这虽然看起来非常显然,但实际上还是要写一下的。为方便理解不用sigma了。。

F(x) = a_0x^0 + a_1x^1 + a_2x^2 +...+a_nx^n

给它差分一下

\Delta F(x) = a_1 + a_2[x^2-(x-1)^2]+...+a_n[x^n-(x-1)^n]

这里的关键在于,x^n-(x-1)^n 算出来一定是一个n-1次多项式。(二项式定理展开就显然了(实际上本来就很显然))

也就是说,一个n次多项式每进行一次差分就会变成n-1次多项式。因此,原题的n次多项式进行操作后一定会变成一个常量函数

这里也证明了一点,求f(\infin )等价于求f(n)(因为从n开始后面全是常量。

到这里总结一下,也就是说,虽然从原题看起来差分n次后是一个找不到规律的奇怪的式子,但是它从第n项起的常量就等于对原多项式进行n次差分后的常函数。我们现在的目标变成了求题目给出的函数差分n次后的结果。

Step Three

怎么求函数差分n次后的结果呢?

首先,根据数列差分的定义,我们知道如果 F(x) = f_1(x) + f_2(x) 那么显然\Delta F(x) = \Delta f_1(x) + \Delta f_2(x) 也就是说,n次多项式函数的差分可以分成n个单项式作为函数求差分的和。n个单项式的次数是从0n的。也就是说,其中有n-1个都会变成0。(把一个低于n次的多项式差分n次显然会变成0)

也就是说,比如

F(x) = a_0x^0 + a_1x^1 + a_2x^2 +...+a_nx^n

\Delta F(x) = \Delta f(x)其中f(x) = a_0x^n

把系数a_0提出去,下面就是求x^nn阶差分。

Step Four

非常显然,对x^nn阶差分等价于对x^n求一次差分后再进行n-1次差分。

先尝试进行一次差分

\Delta (x^n) = x^n - (x-1)^{n}

= x^n - \sum_{k=0}^n \bigl( \begin{smallmatrix} n \k \end{smallmatrix} \bigr)(-1)^{n-k}x^k

= - \sum_{k=0}^n \bigl ( \begin{smallmatrix} n \k \end{smallmatrix} \bigr)  (-1)^{n-k} x^k

这里就是一个二项式定理的展开。然后又变成了n-1次。对n-1次求差分又只需要最高位。也就是,这里需要保留的系数是(\begin{smallmatrix} n \n-1 \end{smallmatrix} \bigr) = n

最后把所有的系数提出来,就是n!然后乘上最前面的常数a_n

因此 答案 a_n n!

Step Five

实现

n 1e9

~~我还真只会打表~~

一些和数学有关的东西

感谢zbww神仙讲数学实在有用!!QWQ STO zbww Orz

1. 递推k次幂和

S_k{n} = \sum_{i=1}^n i^k

S_k(n) + (n+1)^k

= 1 + \sum_{i=1}^n (i+1)^k

= 1 + \sum_{i=1}^n \sum_{j=0}^k i^j \bigl( \begin{smallmatrix} k \ j \end{smallmatrix} \bigr)

= 1 + \sum_{j=0}^k \bigl( \begin{smallmatrix} k \ j \end{smallmatrix} \bigr) S_j(n)

kS_{k-1}(n) = (n+1)^k - 1 - \sum_{j=0}^{k-2} \bigl( \begin{smallmatrix} k \ j  \end{smallmatrix} \bigr) S_j(n)

2. 概率相关

E(X + Y) = E(X) + E(Y)

E(XY) = E(X)E(Y)

(当XY为两个独立的事件)

Simple Questions:

1. Max of two You roll a 6-sided die twice. Find EV of the bigger of two scores.

假设这个比较大的值是 X 则 我们只需要统计两个骰子至少有一个是X,另一个比X小的状态数
于是考虑两边都小于等于X状态数 – 两边都小雨X状态数

ans = \frac{\sum_1^6 x( x^2 - (x-1)^2 )}{36}

2. Max of N

显然,上面式子改成N次幂就好

3. First heads Find EV of the number of coin tosses until you get heads.

抛一个硬币,多少次可以找到正面
一次找到正面的概率是1/2,以前只会乱搞ac,现在学到了数学一点的方法
\sum_{x=1}^{\infty} x(\frac{1}{2})^x

看这个玩意趋近于多少,用到一个公式

\sum_{x=1}^{\infty} a^x = \frac{1}{1-x}

非常重要!

然后

a-\frac{1}{2}a = 2-1 a = 2

4. ex: 连续抛一个骰子,期望多少次抛到6

第一次丢出6的概率\frac{1}{6}

刚好在第i次丢到6的概率
(\frac{5}{6})^{i-1}\times(\frac{1}{6})

求期望就是\sum_{i=1}^\infty i\frac{1}{6}(\frac{5}{6})^{i-1} = \frac{1}{6}\sum_{i=1}^\infty i(\frac{5}{6})^{i-1} = \frac{1}{6}\sum_{i=0}^\infty (i+1)(\frac{5}{6})^{i}

t = \sum_{i=0}^\infty (i+1)(\frac{5}{6})^i

t - \frac{5}{6}t = \sum_{i=0}^\infty (\frac{5}{6})^i = \frac{1}{1-\frac{5}{6}} = 6

t = 36

ans = 6

5.Two heads in a row Find EV of the number of coin tosses until you get heads two times in a row.

一直抛一枚硬币,一直到连续两次出现正面停止

x1表示已经结尾有一个正面,期望还要多少次

x0表示结尾没有正面,期望还要多少次

然后解方程:

x_1 = \frac{1}{2}x_0 + 1
x_0 = \frac{1}{2}x_1 + \frac{1}{2}x_0 + 1

当然还有个比较神仙的解法

还有,假设你活到第i轮,然后这一轮你是正面的概率是fi,这一轮是反面的是gi

则你活到第i轮的概率是 F_i = f_i + g_i

那么有

然后就是个和斐波拉契数列很像的东西!

暂时更这么多吧((挖坑挖坑

等比矩阵列?(大雾)

感谢zbww&fstqwq提供第一种神仙思路。。

好的,让我们看看这个沙雕题

G+G^1+G^2+G^3+...+G^k

如果G是个整数咋搞

显然(对我不显然)快速幂

f(k) = G+G^2+G^3+...+G^k

可以这么转移(Latex不会写矩阵太菜了)

(1 G)( f(i) ) = ( f(i+1) )
(0 G)( G^i )    ( G^{i+1})

然后矩阵快速幂
但是快速幂的矩阵里面还有一个矩阵

详情见分块矩阵不多说

思路2,我这种巨弱能想到的。。

对于k的奇偶性分开考虑

k偶数 化成 (G^1+G^2+...+G^{\frac{k}{2}})\times(E+G^{\frac{k}{2}})

如果是偶数,加上G^k,其中 E是单位矩阵

复杂度。。懒得算。。肯定是log级别的。。

好了推荐一个类似的题:(感觉可以这么跑。。题解说爆精度那我也没办法了)

P3597

[POI2015]WYC

传送
本人trl,不会a*启发式搜索。。

看到权值1,2,3显然拆点。

然后既然要问你第k短路径,可以考虑枚举长度为1路径有多少,长度为2有多少,找到第一个长度使得路径个数达到k

凡一步一步跳的都考虑倍增

然后就显然想到了倍增。

倍增处理后再一个一个减下来,复杂度降到log

最终复杂度~~大概~~是~~O(跑得过)~~O(n^3logk)

当然,有个坑是你不能把拆点拆出的新点用来做路径终点QAQ
因为这个点根本不存在

然后如果倍增到了65还没发现大于k(2^{65}已经炸了)肯定无解。

细节很多 处理一下~~因为一个中间变量没开longlongwa了几十遍~~

/*Heroes Never Die!*/
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 125
#define P 1000000000
typedef long long ll;
ll n , t , k;

struct matrx { ll a[MAXN][MAXN]; } G[70] , tmp , cur , inf ;

bool work( matrx& a ){
    ll p = 0;
    for( ll i = 1 ; i <= n ; ++ i )
        if( (k <= (p += a.a[i][0] - 1)) ) return true;
    return false;
}

void mul( matrx& x , matrx& y ) {
    for( ll i = 0 ; i <= 3*n ; ++ i )
        for( ll j = 0 ; j <= 3*n ; ++ j ) {
            tmp.a[i][j] = 0;
            for( ll p = 0 ; p <= 3*n ; ++ p ) 
                tmp.a[i][j] += x.a[i][p] * y.a[p][j];
        }
}


int main() {
    //freopen("input","r",stdin);
    ll m;
    cin >> n >> m >> k;
    G[0].a[0][0] = 1;
    for( ll i = 1 ; i <= n ; ++ i ) cur.a[i][i] = G[0].a[i][0] = G[0].a[i][i+n] = G[0].a[i+n][i+2*n] = 1;
    for( ll i = 0,u,v,w ; i < m ; ++ i ) {
        scanf("%lld%lld%lld",&u,&v,&w);
        ++ G[0].a[u+(w-1)*n][v];
    }
    ll i;
    for( i = 1 ;  ; ++ i ) {
        if( i > 65 ) return puts("-1"),0;
        mul( G[i-1] , G[i-1] ) , G[i] = tmp;
        if(work( G[i] )) break;
    }
    long long ans = 0;
    for( i-- ; ~i ; --i ) {
        mul( cur , G[i] );
        if( !work(tmp) ) cur = tmp , ans += (1ll<<i);
    }
    cout << ans ;
}
//qwq



主席树入门

板子题: 静态区间rankk。。

首先考虑建立一棵权值线段树。如果在权值线段树上求整个区间的rankk是非常简单的

但是如果求的不是整个区间而是一个静态区间呢?

我们发现rankk操作是可减的。如果我们可以快速求出[1,r]和[1,l]的个数的差就可以求出rankk

既然要求[1,r]和[1,l],非常容易想到权值线段树动态加点。但是我们在加入r这个位置的时候还需要访问l这个时刻的树。

于是考虑对线段树可持久化,这样就可以快速访问历史版本。首先把1到n的数字依次加入这课主席树,然后每次询问只需要访问加入l和加入r的两个版本的数字差就好。

说的不是很清楚啊

怎么做到可持久呢

当然,如果可以树状数组就更方便,但是貌似不好可持久(巨佬们说可以可持久但是我不会网上也没教程)

考虑可持久权值线段树。

由于是单点修改,每一次只修改从根到叶子的一个路径,修改只用了logn的空间。所以可以考虑把每次修改后的路径给存一下。

于是空间需要O(n+qlogn+eps)这么大

代码:

/*Heroes Never Die!*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 200006

int id,cnt , sum[MAXN*21] , ls[MAXN*21], rs[MAXN*21] , rt[MAXN*21];

void build( int& k ,int l ,int r ) {
    k = ++id;
    if( l == r ) return;
    int m = l + r >> 1;
    build( ls[k], l , m ) , build( rs[k], m + 1 , r );
}
void change( int old , int& k , int l , int r , int p , int x ) {
    k = ++id , ls[k] = ls[old] , rs[k] = rs[old];
    sum[k] = sum[old] + x;
    if( l == r ) return;
    int m = l + r >> 1;
    if( p <= m ) change( ls[old] , ls[k] , l , m , p , x );
    else change( rs[old] , rs[k] , m + 1 , r , p , x );
}
int query( int old , int cur , int l , int r , int k ) {
    if( l == r ) return l;
    int cursum = sum[ls[cur]] - sum[ls[old]] , m = l + r >> 1;
    if( cursum >= k ) return query( ls[old] , ls[cur] , l,m,k );
    else return query( rs[old],rs[cur],m+1,r,k-cursum );
} 

int n , A[MAXN] , idx[MAXN] , m;
int main() {
    //freopen("input","r",stdin);
    cin >> n >> m;
    for( int i = 1 ; i <= n ; ++ i ) scanf("%d",&A[i]) , idx[i] = A[i];
    sort( idx + 1 , idx + 1 + n );
    cnt = unique( idx + 1 , idx + 1 + n ) - idx - 1;
    build( rt[0] , 1 , cnt );
    for( int i = 1 ; i <= n ; ++ i ) 
        A[i] = lower_bound( idx + 1, idx + cnt + 1 , A[i] ) - idx;
    for( int i = 1; i <= n ;++ i ) change( rt[i-1] , rt[i] , 1,cnt,A[i],1 );
    for( int i = 1,u,v,k ; i <= m ; ++ i ) 
        scanf("%d%d%d",&u,&v,&k) , printf("%d\n",idx[query(rt[u-1],rt[v],1,cnt,k)]); 
}


luoguP2824 [HEOI2016/TJOI2016]排序

题很好但是我不会

二分答案%%%

二分一下询问位置的值。然后把整个序列变成一个01序。如果一个数字大于等于它就看成1,如果小于等于就看成0.

然后对所有待处理区间排序。这里由于是01序,排序只需要
1.统计1的个数
2.全部清0
3.后面/前面部分赋1

这是个显然的线段树操作,但是我打了ODT

于是wa了

填坑 今天发现了以前代码的漏洞

首先,正解线段树窝也打了

/*Heroes Never Die!*/
#include "iostream"
#include "cstring"
#include "cstdio"
#include "set"
#include "algorithm"
using namespace std;
#define MAXN 50006
int A[MAXN] , k , n , m;

struct query { int l , r , k ; } q[MAXN];

int S[MAXN<<2] , lazy[MAXN<<2];

void pushup( int rt ) {
    S[rt] = S[rt<<1] + S[rt<<1|1];
}

void pushdown( int rt , int m ) {
    if( lazy[rt] == 1 ) {
        S[rt<<1] = ( m - ( m >> 1 ) ) , S[rt<<1|1] = ( m >> 1 );
        lazy[rt<<1] = 1, lazy[rt<<1|1] = 1, lazy[rt] = 0;
    }
    if( lazy[rt] == -1 ) {
        S[rt<<1] = 0 , S[rt<<1|1] = 0 ,
        lazy[rt<<1] = -1 , lazy[rt<<1|1] = -1 , lazy[rt] = 0;
    }
}

void build( int l , int r , int rt , int x ) {
    if( l == r ) {if( A[l] >= x ) S[rt] = 1;else S[rt] = 0;return;}
    int m = l + r >> 1;
    build( l , m , rt<<1 , x );
    build( m + 1 , r , rt<<1|1, x );
    pushup( rt );
}

void change( int L , int R , int c, int l=1 , int r = n , int rt = 1 ) {
    if( L <= l && R >= r ) { S[rt] = c?(r-l+1):0 , lazy[rt] = c?1:-1; return; }
    int m = l + r >> 1;
    pushdown( rt , r - l + 1 );
    if( L <= m ) change( L,R,c,l,m,rt<<1 );
    if( R >  m ) change( L,R,c,m+1,r,rt<<1|1 );
    pushup( rt );
}

int countone( int L , int R , int l = 1 , int r = n , int rt = 1 ) {
    if( L <= l && R >= r ) return S[rt];
    int m = l + r >> 1 , res = 0;
    pushdown( rt , r - l + 1 );
    if( L <= m ) res += countone( L,R,l,m,rt<<1 );
    if( R >  m ) res += countone( L,R,m+1,r,rt<<1|1 );
    return res;
}

bool check( int x ) {
    memset( S,0,sizeof S ) , memset( lazy , 0 , sizeof lazy );
    build( 1,n,1,x );
    for( int i = 1 ; i <= m ; ++ i ) {
        int l = q[i].l , r = q[i].r , k = q[i].k , numone = countone( l , r );
        if( !k ) change( r - numone + 1 , r , 1 ) , change( l , r - numone , 0 );
        else change( l , l + numone - 1 , 1 ) , change( l + numone , r , 0 );
    }
    return countone( k,k ) == 1;
}

int main() {
    cin >> n >> m;
    for( int i = 1 ; i <= n ; ++ i ) scanf( "%d" , & A[i] );
    for( int i = 1 ; i <= m ; ++ i ) scanf( "%d%d%d" , &q[i].k , &q[i].l , &q[i].r);
    cin >> k;
    int l = 1 , r = n , m , ans;
    while( l <= r ) {
        m = l + r >> 1;
        if( check(m) ) ans = m , l = m + 1;//最后这个位置上是1 , 那么选的数字大了
        else r = m - 1;
    }
    cout << ans;
}

然后ODT 开O2 随便跑

// luogu-judger-enable-o2
/*Heroes Never Die!*/
#include "iostream"
#include "cstring"
#include "cstdio"
#include "set"
#include "algorithm"
using namespace std;
#define MAXN 100006
int A[MAXN] , k , n , m;

struct query { int l , r , k ; } q[MAXN];

struct node{
    int l , r , v;
    node( int l , int r = -1 , int v = 0 ) :l(l) , r(r) ,v(v) {}
    node( ) {}
    bool operator < ( const node& t ) const {
        return l < t.l;
    }
};

set<node> S;

set<node>::iterator spli( int pos ) {
    auto it = S.lower_bound( node( pos ) );
    if( it != S.end( ) && it->l == pos ) return it; --it;
    int l = it->l , r = it->r , v = it->v;
    S.erase( it ) , S.insert( node( l , pos - 1 , v ) );
    return S.insert( node( pos , r , v ) ).first;
}
int countone( int l ,int r ) {
    auto itr = spli( r + 1 ) , itl = spli( l ); int res = 0;
    for( ; itl != itr ; ++ itl )
        if( itl->v == 1 ) res += itl->r - itl->l + 1;
    return res;
}

void change( int l , int  r , int v ) {
    auto itr = spli( r + 1 ) , itl = spli( l );
    S.erase( itl , itr ) , S.insert( node( l , r , v ) );
}

bool check( int x ) {
    S.clear();
    for( int i = 1 ; i <= n ; ++ i )
        S.insert( node( i , i , A[i] >= x ) );
    S.insert( node( n + 1 , n + 1 , -1 ) );
    for( int i = 1 ; i <= m ; ++ i ) {
        int l = q[i].l , r = q[i].r , k = q[i].k , numone = countone( l , r );
        if( !k ) change( r - numone + 1 , r , 1 ) , change( l , r - numone , 0 );
        else change( l , l + numone - 1 , 1 ) , change( l + numone , r , 0 );
    }
    return spli( k )->v == 1 ;
}

int main() {
    cin >> n >> m;
    for( int i = 1 ; i <= n ; ++ i ) scanf( "%d" , & A[i] );
    for( int i = 1 ; i <= m ; ++ i ) scanf( "%d%d%d" , &q[i].k , &q[i].l , &q[i].r);
    cin >> k;
    int l = 1 , r = n , m , ans;
    while( l <= r ) {
        m = l + r >> 1;
        if( check(m) ) ans = m , l = m + 1 ;//最后这个位置上是1 , 那么选的数字大了
        else r = m - 1;
    }
    cout << ans;
}

题真的敲好的说

[SCOI2009]迷路

看到题,如果边权都是1就很好做了(矩阵快速幂一波带走)

但是呢。。。

这题边权有10 啊??

zjk 太巨了。。

拆点。。 比如一个点到另一个是8,那么就拆成八个边权为1,前七个只和后一个相连,最后一个和下一个相连。思路和分层图很像。
不多说了。。

/**************************************************************
    Problem: 1297
    User: yi_han
    Language: C++
    Result: Accepted
    Time:2100 ms
    Memory:1416 kb
****************************************************************/

/*Heroes Never Die!*/
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define MAXN 101
#define P 2009

int n , t , k;

struct matrx { int a[MAXN][MAXN]; } G , ans , tmp ;

void mul( matrx x , matrx y ) {
    for( int i = 1 ; i < MAXN ; ++ i )
        for( int j = 1 ; j < MAXN ; ++ j ) {
            tmp.a[i][j] = 0;
            for( int p = 1 ; p < MAXN ; ++ p )
                tmp.a[i][j] += x.a[i][p] * y.a[p][j] , tmp.a[i][j] %= P;
        }
}

void work( int k ) {
    while( k ) {
        if( k & 1 ) mul( ans , G ) , ans = tmp ;
        k >>= 1 , mul( G , G ) , G = tmp;
    }
}

int main() {
    cin >> n >> t;
    for( int i = 1 ; i <= n ; ++ i )
        for( int j = 1 ; j <= n ; ++ j ){
            scanf("%1d" , &G.a[i][j]);
            k = 1;
            while( G.a[i][j] > 1) G.a[i + (k-1) * n][i + k * n] = 1 , --G . a[i][j] , ++ k;
            if( G.a[i][j] ) G.a[i][j] = 0 , G.a[i + (k-1)*n][j] = 1;
        }
    for( int i = 1 ; i < MAXN ; ++ i ) ans.a[i][i] = 1;
    work( t );
    cout << ans.a[1][n];
}

最短路有四种写法你知道吗?

你是应当知道的,将来noi赛场要用。

当然,这是用来存高精模版的

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const double PI = acos(-1.0);
struct Complex{
    double x,y;
    Complex(double _x = 0.0,double _y = 0.0){
        x = _x;
        y = _y;
    }
    Complex operator-(const Complex &b)const{
        return Complex(x - b.x,y - b.y);
    }
    Complex operator+(const Complex &b)const{
        return Complex(x + b.x,y + b.y);
    }
    Complex operator*(const Complex &b)const{
        return Complex(x*b.x - y*b.y,x*b.y + y*b.x);
    }
};
/*
 *进行DFT和IDFT前的反置变换
 *位置i和i的二进制反转后的位置互换
 *len必须为2的幂
 */
void change(Complex y[],int len){
    int i,j,k;
    for(int i = 1,j = len/2;i<len-1;i++){
        if(i < j)    swap(y[i],y[j]);
        //交换互为小标反转的元素,i<j保证交换一次
        //i做正常的+1,j做反转类型的+1,始终保持i和j是反转的
        k = len/2;
        while(j >= k){
            j = j - k;
            k = k/2;
        }
        if(j < k)    j+=k;
    }
}
/*
 *做FFT
 *len必须是2^k形式
 *on == 1时是DFT,on == -1时是IDFT
 */
void fft(Complex y[],int len,int on){
    change(y,len);
    for(int h = 2;h <= len;h<<=1){
        Complex wn(cos(on*2*PI/h),sin(on*2*PI/h));
        for(int j = 0;j < len;j += h){
            Complex w(1,0);
            for(int k = j;k < j + h/2;k++){
                Complex u = y[k];
                Complex t = w*y[k + h/2];
                y[k] = u + t;
                y[k + h/2] = u - t;
                w = w*wn;
            }
        }
    }
    if(on == -1){
        for(int i = 0;i < len;i++){
            y[i].x /= len;
        }
    }
}
class BigInt
{
#define Value(x, nega) ((nega) ? -(x) : (x))
#define At(vec, index) ((index) < vec.size() ? vec[(index)] : 0)
    //C风格的比较函数,其正负等于abs(lhs)-abs(rhs)的正负
    static int absComp(const BigInt &lhs, const BigInt &rhs)
    {
        if (lhs.size() != rhs.size())
            return lhs.size() < rhs.size() ? -1 : 1;
        for (int i = lhs.size() - 1; i >= 0; --i)
            if (lhs[i] != rhs[i])
                return lhs[i] < rhs[i] ? -1 : 1;
        return 0;
    }
    using Long = long long;
    const static int Exp = 9;
    const static Long Mod = 1000000000;
    mutable std::vector<Long> val;
    mutable bool nega = false;
    //规定:0的nega必须是false,0的size必须是0
    void trim() const
    {
        while (val.size() && val.back() == 0)
            val.pop_back();
        if (val.empty())
            nega = false;
    }
    int size() const { return val.size(); }
    Long &operator[](int index) const { return val[index]; }
    Long &back() const { return val.back(); }
    BigInt(int size, bool nega) : val(size), nega(nega) {}
    BigInt(const std::vector<Long> &val, bool nega) : val(val), nega(nega) {}

public:
    friend std::ostream &operator<<(std::ostream &os, const BigInt &n)
    {
        if (n.size())
        {
            if (n.nega)
                putchar('-');
            for (int i = n.size() - 1; i >= 0; --i)
            {
                if (i == n.size() - 1)
                    printf("%lld", n[i]);
                else
                    printf("%0*lld", n.Exp, n[i]);
            }
        }
        else
            putchar('0');
        return os;
    }
    friend BigInt operator+(const BigInt &lhs, const BigInt &rhs)
    {
        BigInt ret(lhs);
        return ret += rhs;
    }
    friend BigInt operator-(const BigInt &lhs, const BigInt &rhs)
    {
        BigInt ret(lhs);
        return ret -= rhs;
    }
    BigInt(Long x = 0)
    {
        if (x < 0)
            x = -x, nega = true;
        while (x >= Mod)
            val.push_back(x % Mod), x /= Mod;
        if (x)
            val.push_back(x);
    }
    BigInt(const char *s)
    {
        int bound = 0, pos;
        if (s[0] == '-')
            nega = true, bound = 1;
        Long cur = 0, pow = 1;
        for (pos = strlen(s) - 1; pos >= Exp + bound - 1; pos -= Exp, val.push_back(cur), cur = 0, pow = 1)
            for (int i = pos; i > pos - Exp; --i)
                cur += (s[i] - '0') * pow, pow *= 10;
        for (cur = 0, pow = 1; pos >= bound; --pos)
            cur += (s[pos] - '0') * pow, pow *= 10;
        if (cur)
            val.push_back(cur);
    }
    BigInt &operator=(const char *s){
        BigInt n(s);
        *this = n;
        return n;
    }
    BigInt &operator=(const Long x){
        BigInt n(x);
        *this = n;
        return n;
    }
    friend std::istream &operator>>(std::istream &is, BigInt &n){
        string s;
        is >> s;
        n=(char*)s.data();
        return is;
    }
    BigInt &operator+=(const BigInt &rhs)
    {
        const int cap = std::max(size(), rhs.size()) + 1;
        val.resize(cap);
        int carry = 0;
        for (int i = 0; i < cap - 1; ++i)
        {
            val[i] = Value(val[i], nega) + Value(At(rhs, i), rhs.nega) + carry, carry = 0;
            if (val[i] >= Mod)
                val[i] -= Mod, carry = 1; //至多只需要减一次,不需要取模
            else if (val[i] < 0)
                val[i] += Mod, carry = -1; //同理
        }
        if ((val.back() = carry) == -1) //assert(val.back() == 1 or 0 or -1)
        {
            nega = true, val.pop_back();
            bool tailZero = true;
            for (int i = 0; i < cap - 1; ++i)
            {
                if (tailZero && val[i])
                    val[i] = Mod - val[i], tailZero = false;
                else
                    val[i] = Mod - 1 - val[i];
            }
        }
        trim();
        return *this;
    }
    friend BigInt operator-(const BigInt &rhs)
    {
        BigInt ret(rhs);
        ret.nega ^= 1;
        return ret;
    }
    BigInt &operator-=(const BigInt &rhs)
    {
        rhs.nega ^= 1;
        *this += rhs;
        rhs.nega ^= 1;
        return *this;
    }
    /*要速度损失精度
    friend BigInt operator*(const BigInt &lhs, const BigInt &rhs)
    {
        int len=1;
        BigInt ll=lhs,rr=rhs;
        ll.nega = lhs.nega ^ rhs.nega;
        while(len<2*lhs.size()||len<2*rhs.size())len<<=1;
        ll.val.resize(len),rr.val.resize(len);
        Complex x1[len],x2[len];
        for(int i=0;i<len;i++){
            Complex nx(ll[i],0.0),ny(rr[i],0.0);
            x1[i]=nx;
            x2[i]=ny;
        }
        fft(x1,len,1);
        fft(x2,len,1);
        for(int i = 0 ; i < len; i++)
            x1[i] = x1[i] * x2[i];
        fft( x1 , len , -1 );
        for(int i = 0 ; i < len; i++)
            ll[i] = int( x1[i].x + 0.5 );
        for(int i = 0 ; i < len; i++){
            ll[i+1]+=ll[i]/Mod;
            ll[i]%=Mod;
        }
        ll.trim();
        return ll;
    }
//*/
//*要精度拖慢速度
    friend BigInt operator*(const BigInt &lhs, const BigInt &rhs)
    {
        const int cap = lhs.size() + rhs.size() + 1;
        BigInt ret(cap, lhs.nega ^ rhs.nega);
        //j < l.size(),i - j < rhs.size() => i - rhs.size() + 1 <= j
        for (int i = 0; i < cap - 1; ++i) // assert(0 <= ret[cap-1] < Mod)
            for (int j = std::max(i - rhs.size() + 1, 0), up = std::min(i + 1, lhs.size()); j < up; ++j)
            {
                ret[i] += lhs[j] * rhs[i - j];
                ret[i + 1] += ret[i] / Mod, ret[i] %= Mod;
            }
        ret.trim();
        return ret;
    }
//*/
    friend BigInt operator*(const BigInt &lhs, const Long &x){
        BigInt ret=lhs;
        bool negat = ( x < 0 );
        Long xx = (negat) ? -x : x;
        ret.nega ^= negat;
        ret.val.push_back(0);
        ret.val.push_back(0);
        for(int i = 0; i < ret.size(); i++)
            ret[i]*=xx;
        for(int i = 0; i < ret.size(); i++){
            ret[i+1]+=ret[i]/Mod;
            ret[i] %= Mod;
        }
        ret.trim();
        return ret;
    }
    BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; }
    BigInt &operator*=(const Long &x) { return *this = *this * x; }
    friend BigInt operator/(const BigInt &lhs, const BigInt &rhs)
    {
        static std::vector<BigInt> powTwo{BigInt(1)};
        static std::vector<BigInt> estimate;
        estimate.clear();
        if (absComp(lhs, rhs) < 0)
            return BigInt();
        BigInt cur = rhs;
        int cmp;
        while ((cmp = absComp(cur, lhs)) <= 0)
        {
            estimate.push_back(cur), cur += cur;
            if (estimate.size() >= powTwo.size())
                powTwo.push_back(powTwo.back() + powTwo.back());
        }
        if (cmp == 0)
            return BigInt(powTwo.back().val, lhs.nega ^ rhs.nega);
        BigInt ret = powTwo[estimate.size() - 1];
        cur = estimate[estimate.size() - 1];
        for (int i = estimate.size() - 1; i >= 0 && cmp != 0; --i)
            if ((cmp = absComp(cur + estimate[i], lhs)) <= 0)
                cur += estimate[i], ret += powTwo[i];
        ret.nega = lhs.nega ^ rhs.nega;
        return ret;
    }
    friend BigInt operator/(const BigInt &num,const Long &x){
        bool negat = ( x < 0 );
        Long xx = (negat) ? -x : x;
        BigInt ret;
        Long k = 0;
        ret.val.resize( num.size() );
        ret.nega = (num.nega ^ negat);
        for(int i = num.size() - 1 ;i >= 0; i--){
            ret[i] = ( k * Mod + num[i]) / xx;
            k = ( k * Mod + num[i]) % xx;
        }
        ret.trim();
        return ret;
    }
    bool operator==(const BigInt &rhs) const
    {
        return nega == rhs.nega && val == rhs.val;
    }
    bool operator!=(const BigInt &rhs) const { return nega != rhs.nega || val != rhs.val; }
    bool operator>=(const BigInt &rhs) const { return !(*this < rhs); }
    bool operator>(const BigInt &rhs) const { return !(*this <= rhs); }
    bool operator<=(const BigInt &rhs) const
    {
        if (nega && !rhs.nega)
            return true;
        if (!nega && rhs.nega)
            return false;
        int cmp = absComp(*this, rhs);
        return nega ? cmp >= 0 : cmp <= 0;
    }
    bool operator<(const BigInt &rhs) const
    {
        if (nega && !rhs.nega)
            return true;
        if (!nega && rhs.nega)
            return false;
        return (absComp(*this, rhs) < 0) ^ nega;
    }
    void swap(const BigInt &rhs) const
    {
        std::swap(val, rhs.val);
        std::swap(nega, rhs.nega);
    }
};
BigInt ba,bb;
int main(){
    cin>>ba>>bb;
    std::cout << ba + bb << '\n';//和
    std::cout << ba - bb << '\n';//差
    std::cout << ba * bb << '\n';//积
    BigInt d;
    std::cout << (d = ba / bb) << '\n';//商
    std::cout << ba - d * bb << '\n';//余
    return 0;
}

序列操作

%%% lxl tql orz

ODT tql%%%

odt大法吼啊。。


扯淡结束

确实 这个odt 好写。。只是会被对着卡掉。。。

一定记住 把 split r+1 写在l前面,,,因此re*n。。。

/*Heroes Never Die!*/
#include "iostream"
#include "cstring"
#include "cstdio"
#include "set"
#include "algorithm"
#define auto set<node>::iterator
using namespace std;
struct node{
    int l , r ;
    mutable int v ;
    node( int l , int r = -1 , int v = 0 ) : l( l ) , r( r ) , v( v ) {}
    bool operator < ( const node & x ) const {
        return x . l > l;
    }
};
set< node > S;
int n , m ;
void build( ) {
    for( int i = 0 , u ; i < n ; ++ i )
        scanf("%d",&u), S.insert( node( i , i , u ) );
}
set<node>::iterator split( int pos ) {
    auto it = S . lower_bound( node( pos ) );
    if( it != S.end() && it -> l == pos ) return it;
    -- it;
    int l = it -> l , r = it -> r , v = it -> v;
    S.erase( it ) , S.insert( node( l , pos - 1 , v ) );
    return S.insert( node( pos , r , v ) ).first;
}
void assign( int l , int r , int v ) {
    auto R = split( r + 1 ) , L = split( l ) ;
    S.erase( L , R ) , S.insert( node( l , r , v ) );
}
void reverse( int l , int r ) {
    auto R = split( r + 1 ) , L = split( l ) ;
    for( ; L != R ; ++ L ) L -> v ^= 1;
}
int count ( int l , int r ) {
    int res = 0;
    auto R = split( r + 1 ) , L = split( l ) ;
    for( ; L != R ; ++ L ) if( L -> v == 1 )
        res += L -> r - L -> l + 1;
    return res;
}
int work ( int l , int r ) {
    int cur = 0 , ans = 0;
    auto  R = split( r + 1 ) , L = split( l ) ;
    for( ; L != R ; ++ L )
        if(L -> v == 1)
            cur += ( L -> r - L -> l + 1 );
        else ans = max( ans , cur ) , cur = 0;
    return max( ans , cur );
}
int main(){
    cin >> n >> m;
    build();
    S.insert( node( n , n , 0 ) );
    for( int i = 0 , opt , u , v ; i < m ; ++ i ){
        scanf("%d%d%d" , &opt , &u , &v ) ;
        if( opt == 0 ) assign( u , v , 0 );
        else if( opt == 1 ) assign( u , v , 1 );
        else if( opt == 2 ) reverse( u , v );
        else if( opt == 3 ) printf( "%d\n" , count( u , v ) );
        else if( opt == 4) printf( "%d\n" , work( u , v ) );
    }
}