图书列表

时间限制: 1Sec   内存限制: 256MB
标准输入   标准输出

Description

小 G 发现图书馆里的电子图书通过列表进行分类,例如下面 5 本书的位置可以表示为:

  1. MATH / GRAPH THEORY
  2. ART / HISTORY / JAPANESE HISTORY / JAPANESE ACIENT HISTORY
  3. ART / HISTORY / CHINESE HISTORY / THREE KINDOM / RESEARCHES ON LIUBEI
  4. ART / HISTORY / CHINESE HISTORY / CHINESE MORDEN HISTORY
  5. ART / HISTORY / CHINESE HISTORY / THREE KINDOM / RESEARCHES ON CAOCAO

小 G 认为这份列表很不容易阅读和查找,于是他决定按照以下规则制作一份新列表,用缩进来体现图书与目录之间的层级关系:

  1. 直接隶属于 n 级目录的图书前有 4×n 个空格的缩进。
  2. 直接隶属于目录 X 目录与图书按照字典序列在目录 X 之后,但所有目录位于所有图书之前。
  3. 所有一级目录按照字典序先后列出。

例如,上面的列表转化后将变为:

ART
    HISTORY
        CHINESE HISTORY
            THREE KINDOM
                RESEARCHES ON CAOCAO
                RESEARCHES ON LIUBEI
            CHINESE MORDEN HISTORY
        JAPANESE HISTORY
    JAPANESE ACIENT HISTORY
MATH
    GRAPH THEORY

请写一个程序帮助小 G 完成这项工作。

Input

输入原列表,共包含不超过 30 本图书,以一个数字 0 结尾。 每行列出一个表项,表项是一个由大写字母、数字、“/”和空格构成的字符串,长度不超过 100。 一本图书可能在列表中出现多次,但在转化后的列表中,它应该只出现一次。但是若同名的图书或目录若在不同的目录结构下,则认为他们是不相同的。换句话说,一个图书或目录由以它的名字为结尾的前缀唯一确定。

Output

输出新列表。本试题采用逐字节比较,行末请勿输出多余空格,文末以恰好一个换行符结尾。

Sample Input

B/A
B/A
B/B
0
A1/B1/B32/B7
A1/B/B2/B4/C5
A1/B1/B2/B6/C5
A1/B1/B2/B5
A1/B1/B2
A1/B1/B2/B1
A1/B3/B2
A3/B1
A0/A1
0

Sample Output

B
A
    B
A0
    A1
A1
    B
        B2
            B4
                C5
    B1
        B2
            B6
                C5
            B1
            B5
        B32
            B7
        B2
    B3
        B2
A3
    B1

Solution

我们考虑将原来的结构做成一棵树,我们将所有书的第一个目录连向根。
然后只需要将树的每一层排序,dfs 按序输出即可。

需要注意几个细节:
      以 “/” 分隔点,并实时记录当前位置,方便新建节点
      对操作 3) 我们还需要记录一下每个节点是否为
      注意比较模式不忽略行末空格

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
int cnt=0;
int son[30][5];
bool b[30], o;
string str, now, s[30];
bool cmp (const int &A, const int &B) {
return b[A]<b[B] || (b[A]==b[B]&&s[A]<s[B]);
}
inline void space(int x){x<<=2;while(x--)putchar(' ');}
void dfs(int k, int c) {
if(k) {
if(o) putchar('\n');
space(c), cout<<s[k], o=1;
}
rep(z,1,*son[k]) dfs(son[k][z], c+1);
}
int main() {
while(cin>>str && str[0]!='0') {
int len = str.length(), k=0; // k_当前目录
now="";
bool f;
for(int i=0;i<len;++i) {
if(str[i]=='/') {
f = 0;
rep(z,1,*son[k])if(s[son[k][z]]==now && !b[son[k][z]]) { //相同目录
k = son[k][z];
f = 1; break;
}
if(f) {now="";continue;}
else son[k][++*son[k]]=++cnt, s[k=cnt] = now; //新建目录 进入
now="";
}
else if(i==len-1) {
f = 0; now.push_back(str[i]);
rep(z,1,*son[k])if(s[son[k][z]]==now && b[son[k][z]]) {f = 1; break;} //相同书
if(f) continue;
else son[k][++*son[k]]=++cnt, b[cnt]=1, s[cnt] = now;
}
else now.push_back(str[i]);
}
}
rep(i,0,cnt) sort(son[i]+1, son[i]+*son[i]+1, cmp);
dfs(0, -1);
return 0;
}
/**************************************************************
Problem: 4949
User: ZqlwMatt
Language: C++
Result: 正确
Time:0 ms
Memory:1540 kb
****************************************************************/

量子模型

时间限制: 1Sec   内存限制: 128MB
标准输入   标准输出

Description

小 W 所在学校的物理学水平全国闻名,因此吸引来了大量民间科学爱好者。某一天, 一位自称能做出诺贝尔奖级别成果,颠覆人类物理学框架的民间科学爱好者拦住了小 W, 和小 W 分享了一种小 W 闻所未闻的量子模型:

一个量子的状态可以用一个有序三元组来表示,如果该量子的状态是(x,y,z),则能够发 生如下六种之一的跃迁,转移到另一个状态(如果原状态(x,y,z)满足这种跃迁发生的前提条 件的话)。

前提条件 跃迁后状态
或者
或者
或者
或者
或者
或者

所有的量子的初始状态都是 (i,j,k)(i,j,k),且总满足 i+k=2ji+k=2j,现在对于任意的一个状态 (x,y,z)(x,y,z), 定义三元函数 最少需要 次跃迁可以变成状态 。这位民间科学爱好者同时声称,如果将一个量子一生中所有达到过的看作一个集合 SS,那么 SS 将满足:

  1. S=n|S| = n

他想知道有多少种不同的集合 SS 满足上述条件。

Input

输入文件名为 quantum.in
输入文件包含一行 5 个以空格隔开的整数:i ,j ,k ,n ,mi~, j~, k~, n~, m

Output

输出文件名为 quantum.out
输出文件包含一个整数,表示满足条件的集合 SS 有多少种,为了方便起见,你只要输出这个数字对 20162016 取模的结果。

Sample Input

1 2 3 2 1
1 2 3 3 2

Sample Output

2
4

数据范围

对于 30%30\% 的测试数据
对于 50%50\% 的测试数据
对于 100%100\% 的测试数据

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define drep(i,a,b) for(re i=a;i>=b;--i)
#define mod 2016
int i,j,k,n,m,dp[152][152][2]; //dep num b(m)
int main() {
scanf("%d%d%d%d%d", &i, &j, &k, &n, &m);
dp[m][1][1]=1;
rep(i,1,m) **dp[i] = 1;
drep(dep,m-1,0)
rep(p,0,n)
rep(q,0,p-1) {
(dp[dep][p][0]+=dp[dep+1][q][0]*dp[dep+1][p-q-1][0]) %= mod;
(dp[dep][p][1]+=dp[dep+1][q][1]*dp[dep+1][p-q-1][0]
+dp[dep+1][q][0]*dp[dep+1][p-q-1][1]
+dp[dep+1][q][1]*dp[dep+1][p-q-1][1]) %= mod;
}
printf("%d\n", dp[0][n][1]);
return 0;
}
/**************************************************************
Problem: 4957
User: ZqlwMatt
Language: C++
Result: 正确
Time:12 ms
Memory:1136 kb
****************************************************************/

特教的理性愉悦

时间限制: 1Sec   内存限制: 128MB
标准输入   标准输出

Description

某正教授级特级教师忽然想自娱自乐。于是他准备在纸上画一棵树。这棵树开始时只有 NN 个点,然后特教开始逐条画上一些带权无向边(保证任意时刻纸上的任意两点间至多有一条路径),直到最后形成一棵树。
为了达到理性愉悦的目的,特教在加边的过程中可能会随意选取两个点并取出连接它们的路径,计算该路径上所有点对距离之和(如果已经有路径连通)。例如路径 1 <—5—> 2 <—3—> 3 <—2—> 4,共有 (1,2)(1,3)(1,4)(2,3)(2,4)(3,4) 六个点对,距离之和为 5+8+10+3+5+2=33 。现在特教需要检验他的答案是否正确,于是想请你编个程序帮他验算一下。

Input

输入文件名为 ecstasy.in
第一行为两个正整数 N,MN, M ,表示树的点数和操作数。
第二行开始的 MM 行为 MM 个操作的具体内容,分为两种:

Output

输出文件名为 ecstasy.out
对于每个 (2)(2) 操作输出一行,表示询问的结果。

Sample Input

4 5
1 1 2 5
1 2 3 3
2 1 4
1 3 4 2
2 1 4
10 18
1 2 4 456
1 9 5 801
2 7 3
1 9 7 473
1 9 2 591
1 7 6 409
2 4 2
1 1 7 997
1 3 4 751
1 6 8 576
1 4 10 657
2 4 9
2 2 9
2 9 6
2 4 3
2 10 9
2 7 4
2 9 8

Sample Output

-1
33
-1
456
2094
591
1764
751
5568
5151
4783

数据范围

对于 50%的数据,1N,M20001 \le N,M \le 2000
对于 100%的数据,1N105,1M250000,1w1000 1 \le N \le 10^{5} , 1 \le M \le 250000, 1 \le w \le 1000

Solution

图没画好

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define drep(i,a,b) for(re i=a;i>=b;--i)
const int N = 2e5+5;
typedef long long ll;
inline void read(int &x) {
x=0; int f=1; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
int cnt=0, nxt[N], head[100005], to[N], w[N];
#define add(u,v,W) (nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v,w[cnt]=W)
int f[100005];
int find(int x) {return !f[x]?x:f[x]=find(f[x]);}
int n, m;
struct in {
int type, u, v;
ll ans;
} a[250005];
int fa[100005][21], dis[100005], dep[100005];
ll dis2[100005], dis3[100005];
inline int LCA(int u, int v) {
if(dep[u]<dep[v]) swap(u,v);
drep(i,20,0)if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
if(u==v) return u;
drep(i,20,0)if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
void dfs(int u, int deep=1, int fat=0) {
fa[u][0]=fat, dep[u]=deep; int v;
for(int i=head[u];i;i=nxt[i]) {
v = to[i];
if(v==fat) continue;
dis[v] = dis[u]+w[i];
dis2[v] = dis2[u]+(n-deep)*w[i];
dis3[v] = dis3[u]+1ll*(n-deep)*(n-deep)*w[i];
dfs(v, deep+1, u);
}
}
inline long long calc(int u, int v) {
int lca=LCA(u, v);
int num=dep[u]+dep[v]-2*dep[lca], s1=dis[u]-dis[lca], s2=dis[v]-dis[lca];
ll sum1 = dis2[u]-dis2[lca]-1ll*s1*(n-dep[u]);
ll sum2 = dis2[v]-dis2[lca]-1ll*s2*(n-dep[v]);
ll sum3 = dis3[u]-dis3[lca]-1ll*s1*(n-dep[u])*(n-dep[u])-2ll*(n-dep[u])*sum1;
ll sum4 = dis3[v]-dis3[lca]-1ll*s2*(n-dep[v])*(n-dep[v])-2ll*(n-dep[v])*sum2;
return (sum1+sum2)*(num+1)-sum3-sum4;
}
signed main() {
freopen("ecstasy.in","r",stdin);
freopen("ecstasy.out","w",stdout);
read(n), read(m);
static int opt, u, v, W;
rep(i,1,m) {
read(opt),read(u),read(v);
a[i].type=opt, a[i].u=u, a[i].v=v;
if(opt==1)
read(W), f[find(u)]=find(v), add(u,v,W), add(v,u,W);
else if(find(u)!=find(v)) a[i].ans=-1;
}
dfs(1); rep(i,1,20)rep(x,1,n) fa[x][i]=fa[fa[x][i-1]][i-1];
rep(i,1,m)if(a[i].type==2&&!a[i].ans)a[i].ans=calc(a[i].u,a[i].v);
rep(i,1,m)if(a[i].type==2) printf("%lld\n", a[i].ans);
return 0;
}
/**************************************************************
Problem: 4964
User: ZqlwMatt
Language: C++
Result: 正确
Time:364 ms
Memory:25016 kb
****************************************************************/

好数

时间限制: 1Sec   内存限制: 128MB
标准输入   标准输出

Description

我们定义一个非负整数是“好数”,当且仅当它符合以下条件之一:

  1. 这个数是0或1
  2. 所有小于这个数且与它互质的正整数可以排成一个等差数列

例如,8就是一个好数,因为1,3,5,7排成了等差数列。

给出N个非负整数,然后进行如下三个操作:

  1. 询问区间[L,R]有多少个好数
  2. 将区间[L,R]内所有数对S取余(S≤1000000)
  3. 将第C个数更改为X

Input

输入文件名为 good.in
第一行包含两个正整数 NNMMMM表示操作数目
第二行包含 NN 个非负整数。
接下来的 MM 行每行表示 11 个操作: 表示第 11 个操作, 表示第 22 个操作, 表示第 33 个操作。

Output

输出文件名为 color.out
对每个操作 11,输出一个非负整数,表示区间内好数的个数。

Sample Input

3 6
4 6 9
1 1 3
1 3 3
2 1 1 10
1 1 3
3 2 4
1 1 3

Sample Output

2
0
2
2

Solution

显然操作 1,31,3 可以用线段树维护,我们考虑操作 22

注意到操作 22 是取余操作,那么显然每个数 xx 不可能被连续取余 log2xlog_{2}x 次。
而且每次只能修改一个数,那么对于操作 22 暴力修改即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
const int N = 100002<<2;
inline void read(int &x) {
x=0; int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
int cnt=0, pri[1000000], p[1000002];
inline void init(const int N) {
fill(p, p+1000001, 1);
int t;
rep(i,2,N) {
if(p[i]) pri[++cnt]=i;
for(int j=1;j<=cnt&&(t=i*pri[j])<=N;++j) {
p[t] = 0;
if(i%pri[j]==0) break;
}
}
p[6] = 1;
int bin=1;
while(bin<=N) p[bin]=1, bin<<=1;
}
int n, m, a[100002], S;
int num[N], Max[N];
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
inline void update(int x) {
num[x]=num[lson(x)]+num[rson(x)];
Max[x]=max(Max[lson(x)],Max[rson(x)]);
}
void build(int x, int l, int r) {
if(l==r) {
num[x] = p[a[l]], Max[x] = a[l];
return ;
}
int mid = (l+r)>>1;
build(lson(x), l, mid);
build(rson(x), mid+1, r);
update(x);
}
int get(int x, int l, int r, int ll, int rr) {
if(l==ll && r==rr) return num[x];
int mid = (l+r)>>1;
if(rr<=mid) return get(lson(x), l, mid, ll, rr);
else if(ll>mid) return get(rson(x), mid+1, r, ll, rr);
else return get(lson(x),l,mid,ll,mid)+get(rson(x),mid+1,r,mid+1,rr);
}
void modify(int x,int l,int r,int s,int z) {
if(l==r) {a[l]=z, num[x]=p[z], Max[x]=z;return ;}
int mid = (l+r)>>1;
if(s<=mid) modify(lson(x),l,mid,s,z);
else modify(rson(x),mid+1,r,s,z);
update(x);
}
void mmodify(int x, int l, int r, int ll, int rr ,int S) {
if(l==r) { a[l]%=S, Max[x]=a[l], num[x]=p[a[l]]; return ;}
int mid = (l+r)>>1;
if(Max[lson(x)]>=S&&ll<=mid) mmodify(lson(x), l, mid, ll, rr, S);
if(Max[rson(x)]>=S&&rr>=mid+1) mmodify(rson(x), mid+1, r, ll, rr, S);
update(x);
}
int getMax(int x, int l, int r, int ll, int rr) {
if(l==ll && r==rr) return Max[x];
int mid = (l+r)>>1;
if(rr<=mid) return getMax(lson(x), l, mid, ll, rr);
else if(ll>mid) return getMax(rson(x), mid+1, r, ll, rr);
else return max(getMax(lson(x),l,mid,ll,mid),getMax(rson(x),mid+1,r,mid+1,rr));
}
int main() {
init(1000000);
read(n), read(m);
rep(i,1,n) read(a[i]);
build(1,1,n);
int opt, l, r;
while(m--) {
read(opt);
switch(opt) {
case 1: read(l),read(r),printf("%d\n", get(1,1,n,l,r)); break;
case 2: {
read(l), read(r), read(S);
int tmp = getMax(1,1,n,l,r);
if(tmp<S) continue;
mmodify(1,1,n,l,r,S);
break;
}
case 3: {
read(l), read(S);
modify(1,1,n,l,S);
break;
}
}
}
return 0;
}
/**************************************************************
Problem: 4451
User: ZqlwMatt
Language: C++
Result: 正确
Time:168 ms
Memory:12868 kb
****************************************************************/

峡谷

时间限制: 3Sec   内存限制: 512MB
标准输入   标准输出

Description

给出一个由 nn 个整数 组成的序列。
我们称这个序列的一些连续的段 为一个 峡谷 ,当且仅当 al=ara_{l}=a_{r} ,并且对于所有 l<x<rl < x < r ,都
成立。并定义一个 峡谷 的长度为 rlr-l
特别地,单独的一个数也是一个 峡谷
你的任务是回答 qq 个询问:给定两个数 l,rl,r, 求出 的子段中最大长度的 峡谷

Input

从文件 ravine.in 中读入数据。
输入第一行包含两个正整数 n,qn,q ,表示序列的长度和询问数。
第二行包含 nn 个正整数
接下来的 mm 行,每行包含两个数 li,ril_{i},r_{i} ,表示一个询问。

Output

输出到文件 ravine.out 中。
对于每个询问,输出一个整数,表示所求的最大长度。

Sample Input

8 5
4 3 2 2 3 3 7 3
1 7
6 8
1 3
3 6
1 8

Sample Output

-1
33
4
0
0
1
4

数据范围

对于 的数据,满足

测试点编号 nn qq aia_{i}
1,2,3,41,2,3,4
55
66
7,87,8
9,109,10
11,1211,12 10910^{9}
13,1413,14
1515
1616
17,18,19,2017,18,19,20 10910^{9}

Solution

用ST表。
Max[][] , idMax[][] , idMin[][] 分别维护区间最大值,最大点最左、右端点位置。

f[][] , g[][] 分别维护该点(区间),向左(右)形成 峡谷 的最大距离。

对于询问 l,rl,r,就知道了区间的最大值的最左和最右端点 x,yx,y
显然 ans=max(yx,f(1x1),g(y+1r))ans=max(y-x,f(1 \sim x-1),g(y+1 \sim r))

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define drep(i,a,b) for(re i=a;i>=b;--i)
#define inf 0x3f3f3f3f
#define N 200005
inline void Chkmax(int &a,int b){a=max(a,b);}
inline void Chkmin(int &a,int b){a=min(a,b);}
inline void read(int &x) {
x=0; int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
int n, q, cnt, a[N], b[N];
int Max[N][19], idMax[N][19], idMin[N][19], f[N][19], g[N][19];
int bit[19], Log[N], last[N];
int get(const int &l,const int &r){return max(Max[l][Log[r-l+1]],Max[r-bit[Log[r-l+1]]+1][Log[r-l+1]]);}
inline void init() {
sort(b+1, b+n+1);
cnt = unique(b+1, b+n+1)-b-1;
rep(i,1,n) a[i] = lower_bound(b+1,b+cnt+1,a[i])-b;
bit[0]=1, Log[0]=-1;
rep(i,1,18) bit[i]=bit[i-1]<<1;
rep(i,1,n) Max[i][0]=a[i], idMax[i][0]=idMin[i][0]=i, Log[i]=Log[i>>1]+1;
rep(k,1,Log[n])for(int i=1;i+bit[k]-1<=n;++i) {
if(Max[i][k-1]>Max[i+bit[k-1]][k-1]) {
Max[i][k]=Max[i][k-1];
idMax[i][k]=idMax[i][k-1];
idMin[i][k]=idMin[i][k-1];
}
else if(Max[i][k-1]<Max[i+bit[k-1]][k-1]) {
Max[i][k]=Max[i+bit[k-1]][k-1];
idMax[i][k]=idMax[i+bit[k-1]][k-1];
idMin[i][k]=idMin[i+bit[k-1]][k-1];
}
else {
Max[i][k]=Max[i][k-1];
idMax[i][k]=idMax[i+bit[k-1]][k-1];
idMin[i][k]=idMin[i][k-1];
}
}
// section 1
rep(i,1,n) {
if(!last[a[i]]) g[i][0]=0;
else {
int k = get(last[a[i]],i);
if(k > a[i]) g[i][0]=0;
else g[i][0]=i-last[a[i]]+g[last[a[i]]][0];
}
last[a[i]]=i;
}
rep(k,1,Log[n])for(int i=1;i+bit[k]-1<=n;++i) g[i][k]=max(g[i][k-1],g[i+bit[k-1]][k-1]);
memset(last, 0, sizeof last);
drep(i,n,1) {
if(!last[a[i]]) f[i][0]=0;
else {
int k = get(i,last[a[i]]);
if(k > a[i]) f[i][0]=0;
else f[i][0]=last[a[i]]-i+f[last[a[i]]][0];
}
last[a[i]]=i;
}
rep(k,1,Log[n])for(int i=1;i+bit[k]-1<=n;++i) f[i][k]=max(f[i][k-1],f[i+bit[k-1]][k-1]);
// section 2
}
int main() {
read(n), read(q);
rep(i,1,n) read(a[i]), b[i]=a[i];
init();
static int l, r, res;
while(q--) {
read(l), read(r);
int t=Log[r-l+1], MAX=max(Max[l][t],Max[r-bit[t]+1][t]), ld=inf, rd=0;
if(Max[l][t]==MAX) Chkmin(ld,idMin[l][t]), Chkmax(rd,idMax[l][t]);
if(Max[r-bit[t]+1][t]==MAX) Chkmin(ld,idMin[r-bit[t]+1][t]), Chkmax(rd,idMax[r-bit[t]+1][t]);
res = rd-ld;
--ld, ++rd;
int p=Log[ld-l+1], q=Log[r-rd+1];
if(p>=0) Chkmax(res,max(f[l][p],f[ld-bit[p]+1][p]));
if(q>=0) Chkmax(res,max(g[rd][q],g[r-bit[q]+1][q]));
printf("%d\n", res);
}
return 0;
}

随机数(random)

时间限制: 1Sec   内存限制: 256MB
标准输入   标准输出

Description 众所周知,计算机是无法造出真正的随机数的——通常都是由各种伪随机数生成方法生成的看起来很随机的数。当然,这些伪随机数已经可以满足我们的大多数要求了。

小 F 发现了一个由 CenariusYZ 写的伪随机函数。CenariusYZ 不想给小 F 看他的代码,但告诉他:这个伪随机函数返回的值是一个以调用次数 xx 为变量的一元 nn 次多项式对 998244353998244353 取模得到的值,也即:

其中 mod\text{mod} 为取模操作,并且

CenariusYZ 认为小 F 不可能知道这样他的函数是什么,于是他非常自信地告诉小 F 他 的随机函数在调用某些次数时输出的值是多少。 现在,小 F 想请你帮助他判断这样的随机函数函数是否存在——他觉得 CenariusYZ 可 能在骗他。如果存在的话,也请你告诉他任意一组可能的

Input

从标准输入中读入数据。
输入第 1 行 2 个正整数 n,mn, m,其中 mm 是 CenariusYZ 给他的取值组数。
输入接下来 mm 行,每行 2 个正整数 xi,yix_{i}, y_{i},表示第 xix_{i} 次调用时输出 yiy_{i}

Output

输出到标准输出中。
如果不存在,请输出
如果存在,请输出一行 n+1n + 1 个整数,表示任意一组
你的输出需要满足 ,且 an>0a_{n} > 0

Sample Input

2 3
0 1
1 3
2 7
2 3
0 1
1 1
2 2
0 1
0 2

Sample Output

1 1 1
1 998244352 1
-1

数据范围

样例 1 ,即 (x2+x+1) mod 998244353(x^{2} + x + 1)~\text{mod}~998244353
样例 2,即 。在模意义下,

对于所有数据,有
每个测试点的数据规模及特点如下表:
random

Solution

这道题很容易想到用拉格朗日插值去做。
展开多项式的时候,我们可以先 O(n2)O(n^{2}) 预处理 (xk)\prod(x-k) 。然后每次 O(n)O(n) 除以 (xk)(x-k) 即可。
验证合法性用秦九韶公式算一下就好了。总复杂度 O(n2)O(n^{2})

题目没思维难度,但是考试的时候脑子短路了,预处理上咕咕咕了…
还有要注意验证不合法的解一定要枚举 1~n+1 的所有点验证。

Time: 1542ms / Memory: 3.273MB -O2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define drep(i,a,b) for(re i=a;i>=b;--i)
#define inf 0x3f3f3f3f
#define N 200005
inline void Chkmax(int &a,int b){a=max(a,b);}
inline void Chkmin(int &a,int b){a=min(a,b);}
inline void read(int &x) {
x=0; int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
int n, q, cnt, a[N], b[N];
int Max[N][19], idMax[N][19], idMin[N][19], f[N][19], g[N][19];
int bit[19], Log[N], last[N];
int get(const int &l,const int &r){return max(Max[l][Log[r-l+1]],Max[r-bit[Log[r-l+1]]+1][Log[r-l+1]]);}
inline void init() {
sort(b+1, b+n+1);
cnt = unique(b+1, b+n+1)-b-1;
rep(i,1,n) a[i] = lower_bound(b+1,b+cnt+1,a[i])-b;
bit[0]=1, Log[0]=-1;
rep(i,1,18) bit[i]=bit[i-1]<<1;
rep(i,1,n) Max[i][0]=a[i], idMax[i][0]=idMin[i][0]=i, Log[i]=Log[i>>1]+1;
rep(k,1,Log[n])for(int i=1;i+bit[k]-1<=n;++i) {
if(Max[i][k-1]>Max[i+bit[k-1]][k-1]) {
Max[i][k]=Max[i][k-1];
idMax[i][k]=idMax[i][k-1];
idMin[i][k]=idMin[i][k-1];
}
else if(Max[i][k-1]<Max[i+bit[k-1]][k-1]) {
Max[i][k]=Max[i+bit[k-1]][k-1];
idMax[i][k]=idMax[i+bit[k-1]][k-1];
idMin[i][k]=idMin[i+bit[k-1]][k-1];
}
else {
Max[i][k]=Max[i][k-1];
idMax[i][k]=idMax[i+bit[k-1]][k-1];
idMin[i][k]=idMin[i][k-1];
}
}
// section 1
rep(i,1,n) {
if(!last[a[i]]) g[i][0]=0;
else {
int k = get(last[a[i]],i);
if(k > a[i]) g[i][0]=0;
else g[i][0]=i-last[a[i]]+g[last[a[i]]][0];
}
last[a[i]]=i;
}
rep(k,1,Log[n])for(int i=1;i+bit[k]-1<=n;++i) g[i][k]=max(g[i][k-1],g[i+bit[k-1]][k-1]);
memset(last, 0, sizeof last);
drep(i,n,1) {
if(!last[a[i]]) f[i][0]=0;
else {
int k = get(i,last[a[i]]);
if(k > a[i]) f[i][0]=0;
else f[i][0]=last[a[i]]-i+f[last[a[i]]][0];
}
last[a[i]]=i;
}
rep(k,1,Log[n])for(int i=1;i+bit[k]-1<=n;++i) f[i][k]=max(f[i][k-1],f[i+bit[k-1]][k-1]);
// section 2
}
int main() {
read(n), read(q);
rep(i,1,n) read(a[i]), b[i]=a[i];
init();
static int l, r, res;
while(q--) {
read(l), read(r);
int t=Log[r-l+1], MAX=max(Max[l][t],Max[r-bit[t]+1][t]), ld=inf, rd=0;
if(Max[l][t]==MAX) Chkmin(ld,idMin[l][t]), Chkmax(rd,idMax[l][t]);
if(Max[r-bit[t]+1][t]==MAX) Chkmin(ld,idMin[r-bit[t]+1][t]), Chkmax(rd,idMax[r-bit[t]+1][t]);
res = rd-ld;
--ld, ++rd;
int p=Log[ld-l+1], q=Log[r-rd+1];
if(p>=0) Chkmax(res,max(f[l][p],f[ld-bit[p]+1][p]));
if(q>=0) Chkmax(res,max(g[rd][q],g[r-bit[q]+1][q]));
printf("%d\n", res);
}
return 0;
}