「Wdsr-1」笨蛋结构

ID: 5198

远端评测题

800ms

250MiB

尝试: 0

已通过: 0

难度: 5

上传者:

root

标签>

2020

O2优化

组合数学

差分

题目背景

众所周知，琪露诺是笨蛋。

题目描述

琪露诺希望维护一个长度为 $n$ 的整数序列 $a$ ，初始值都为 $0$ 。

现在琪露诺想要进行 $q$ 次操作，每次选择序列中的一段区间 $[s,s+l-1]$ 并给出两个数字 $w,k$ ，使对所有的 $i \in [1,l]$ ， $a_{s+i-1}$ 加上 $w\times i^k$ 。

琪露诺不希望 $k$ 很大，因此她给出了一个整数 $m$ ，满足 $0\le k\le m$ 。

为了不让头脑简单的琪露诺感到困惑，你只需要输出依次进行完所有操作后，序列中的每个数字对 $2^{64}$ 取模（即 $\text{unsigned long long}$ 自然溢出）后的结果即可。

为了帮助你更好的理解题意，这里给出一段伪代码：

$$\def{\b}#1{\textbf{ #1 }}\def{\t}#1{\text{ #1 }}\def{\s}{\quad} \def{\l}{\underline{\kern{300pt}}\cr[-10pt]} \def{\r}{\overline{\underline{\kern{300pt}}}} \begin{aligned} &\r\cr&\b{Algorithm:}\t{An easy structure}\cr[-13pt]&\l\cr &\begin{aligned} \t{1.}&\b{input}n,m,q \cr \t{2.}&\b{for}i=1\b{to} q \b{do} \cr \t{3.}&\s\b{input} s,l,w,k \cr \t{4.}&\s\b{for} j=1 \b{to} l \b{do}\cr \t{5.}&\s\s a[s+j-1] \gets a[s+j-1]+w\times \t{pow}(j,k) \cr \t{6.}&\s\b{end}\cr \t{7.}&\b{end}\cr \t{8.}&\b{for} i=1 \b{to} n \b{do}\cr \t{9.}&\s\b{output} a[i]\cr \t{10.}&\b{end}\cr \end{aligned}\cr[-12pt] &\r\end{aligned} %Made by @离散小波变换° . %You can find his contributions by searching "JoesSR". $$

其中 $\rm pow(a,b)$ 的含义为 $a^b$ 。

输入格式

请调用下方代码的 input(n,m,q,S,L,W,K) 来输入 $n,m,q,s_i,l_i,w_i,k_i$ 。下标从一开始。

其中 $s,l,w,k$ 的含义与题目描述保持一致。

输出格式

请调用下方代码的 output(n,R) 进行输出。其中 $R_i$ 为所有操作结束后的数列，下标从一开始。

输入数据 1

10 0 5 233

输出数据 1

6942214367

输入数据 2

1000 9 500 6666

输出数据 2

7636746723064426256

提示

样例一说明

生成的数据为：

10 0 5
7 1 1558211206 0
1 3 401324017 0
4 5 235225636 0
6 4 2137131141 0
1 2 3791175968 0

它的结果是：

4192499985 4192499985 401324017 235225636 235225636 2372356777 3930567983 2372356777 2137131141 0

数据生成&数据输出

typedef unsigned long long u64;
typedef unsigned int       u32;
u32 MT[624],idx;
void _init(u32 seed){
    MT[0]=seed; idx=0; for(int i=1;i<624;++i) 
    MT[i]=(0x6c078965*(MT[i-1]^((MT[i-1])>>30)+i));
}
void _gene(){
    for(int i=0;i<624;++i){
        int x=MT[i]&0x80000000+(MT[(i+1)%624]&0x7fffffff);
        MT[i]=MT[(i+397)%624]^(x>>1);
        if(x&2)MT[i]^=0x9908b0df;
    }
}
u32  _calc(){
    if(!idx) _gene(); int x=MT[idx];
    x^=x>>11,x^=(x<<7)&(0x9d2c5680);
    x^=(x<<15)&0xefc60000,x^=x>>18;
    idx=(idx+1)%624; return x;
}
u64 _get(){u64 ret=_calc()*_calc(); return ret;}
u64 _get(u64 _l,u64 _r){return _get()%(_r-_l+1ull)+_l;}
void input(int &_n,int &_m,int &_q,int *_S,int *_L,u64 *_W,int *_K){
    u32 seed; scanf("%d%d%d%u",&_n,&_m,&_q,&seed); _init(seed); int i=1;
    if(_n>100) for(;i<=_q/4;++i){
        int _a=_get(1,_n-100),_b=_get(_a+_m,_a+_m+1),_l=_b-_a+1,_k=_get(0,_m);
        u64 _w=_get(); _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
    if(_n>100) for(;i<=_q/2;++i){
        int _a=_get(1,100),_b=_get(_n-100,_n),_l=_b-_a+1,_k=_get(0,_m);
        u64 _w=_get(); _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
    for(;i<=_q;++i){
        int _a=_get(1,_n),_b=_get(1,_n); if(_a>_b) swap(_a,_b);
        int _l=_b-_a+1,_k=_get(0,_m); u64 _w=_get();
        _S[i]=_a,_L[i]=_l,_W[i]=_w,_K[i]=_k;
    }
}
void output(int n,u64 *R){
    u64 ret=n^_get(); for(int i=1;i<=n;i++) ret^=_get()+R[i];
    printf("%llu\n",ret);
}

其中，调用 input() 读入数据；调用 output() 输出数据。

请勿在任何时候调用除了input和output外的函数，且这两个函数只能调用一次。

数据范围

共 $20$ 个测试点，满足如下条件：

\def\arraystretch{1.5}\begin{array}{|c|c|c|c|}\hline \textbf{编号} & n & m & q \\ \hline [1,3] & \le 3\times 10^3 & =9 & \le 3\times 10^3 \\\hline [4,5] & \le 3\times 10^5 & =0 & \le 3\times 10^5 \\\hline [6,9] & \le 3\times 10^5 & =1 & \le 3\times 10^5 \\\hline [10,13] & \le 3\times 10^5 & =2 & \le 3\times 10^5 \\\hline [14,16] & \le 3\times 10^5 & =9 & \le 3\times 10^5 \\\hline [17,20] & \le 5\times 10^5 & =9 & \le 1\times 10^6 \\\hline \end{array}

其中， $[l,r]$ 表示编号为 $l,l+1,\cdots,r-1,r$ 的测试点。

对于 $100\%$ 的数据，满足 $1\le l_i \le l_i+s_i-1 \le n,0\le k_i\le m,0 \le w\le 2^{64}-1$ 。

#P6308. 「Wdsr-1」笨蛋结构