浴谷八连测R3 题解

A

分类讨论直接前缀和搞搞。

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
/*
Author: CNYALI_LK
LANG: C++
PROG: a.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
const ll p=19260817;
ll dis[204847],fdis[204847],tdis[204847];
ll w[204847],fw[204847],tw[204847],qw[204847];
int main(){
#ifdef cnyali_lk
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
ll n,m,x,l,r;
n=read();
m=read();
for(ll i=1;i<n;++i)dis[i]=read()%p;
for(ll i=1;i<=n;++i){
w[i]=read()%p;
qw[i]=(qw[i-1]+w[i])%p;
}
for(ll i=2;i<=n;++i){
fdis[i]=(dis[i-1]+fdis[i-1])%p;
fw[i]=(fw[i-1]+fdis[i]*w[i])%p;
}
for(ll i=n-1;i;--i){
tdis[i]=(tdis[i+1]+dis[i])%p;
tw[i]=(tw[i+1]+tdis[i]*w[i])%p;
}
for(;m;--m){
x=read();l=read();r=read();
if(x<l){
printf("%lld\n",(fw[r]-fw[l-1]+p-fdis[x]*(qw[r]-qw[l-1]+p)%p+p)%p);
}
else if(r<x){
printf("%lld\n",(tw[l]-tw[r+1]+p-tdis[x]*(qw[r]-qw[l-1]+p)%p+p)%p);
}
else{
printf("%lld\n",((fw[r]-fw[x]+p-fdis[x]*(qw[r]-qw[x])%p+p)+(tw[l]-tw[x]+p-tdis[x]*(qw[x-1]-qw[l-1])%p+p))%p);
}
}
return 0;
}

B

首先显然两部分的区域在各行格列是连续的。 类似于这样:

pic

然后每一行的轮廓线是单调的。

设最大值为Mx,最小值为Mn。

对于答案k,满足一部分Mxk\ge Mx-k(假设为红色),另一部分Mn+k\le Mn+k(假设为蓝色)。

红色可能在左上右上左下右下。

那么就可以通过将这个矩阵旋转90°多次(0,1,2,3次),来使得红色在左上。

二分答案k,贪心的计算红色,判断蓝色是否满足Mn+k\le Mn+k

时间复杂度O(nmlogA)O(nm\log A) A是元素大小。

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
/*
Author: CNYALI_LK
LANG: C++
PROG: b.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
ll a[2047][2047],rj[2047],b[2047][2047];
ll n,m,xmin,xmax;
ll check(ll w){
rj[0]=m;
for(ll i=1;i<=n;++i){
for(rj[i]=0;rj[i]<rj[i-1]&&a[i][rj[i]+1]<=xmin+w;++rj[i]);
for(ll j=rj[i]+1;j<=m;++j)if(a[i][j]<xmax-w)return 0;
}
return 1;
}
void rrotate(){
for(ll i=1;i<=n;++i)for(ll j=1;j<=m;++j)b[j][n-i+1]=a[i][j];
swap(n,m);
for(ll i=1;i<=n;++i)for(ll j=1;j<=m;++j)a[i][j]=b[i][j];
}
int main(){
#ifdef cnyali_lk
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
n=read();
m=read();
xmin=0x3f3f3f3f3f3f3f3f,xmax=0xcccccccccccccccc;
for(ll i=1;i<=n;++i)for(ll j=1;j<=m;++j){a[i][j]=read();chkmin(xmin,a[i][j]);chkmax(xmax,a[i][j]);}
ll ans=0x3f3f3f3f3f3f3f3f,l,r,mid;
for(ll i=0;i<4;++i){
l=0;
r=ans-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid))r=mid-1;
else l=mid+1;
}
ans=r+1;
rrotate();
}
printf("%lld\n",ans);

return 0;
}

C

先考虑给定aia_i无修改的情况。

欧拉定理 : 当bφ(p)b\ge \varphi(p)时,

所以可以通过计算 来计算答案。

大概就是:

1
2
3
4
int query(int l,int r,int p){
if(l==r)return a[l]%p+(a[l]>=p)*a[l];
return calc(a[l],query(l+1,r,phi(p)),p);
}

其中calc(a,b,p)calc(a,b,p)表示计算

正确性显然吧。

但是太慢了。

我们发现,对pp不断地做p=φ(p)p=\varphi(p),很快就会得到1,而1之后就没有必要再算了。

(据说是O(logn)O(\log n)次?)(算出来当p2107p\le 2\cdot 10^7时最多24次)

什么?区间修改?差分完直接树状数组维护就好了。

快速幂是O(logn)O(\log n)的,树状数组也可以O(logn)O(\log n)单点查询。

1
2
3
4
int query(int l,int r,int p){
if(l==r||p==1)return a[l]%p+(a[l]>=p)*a[l];
return calc(a[l],query(l+1,r,phi(p)),p);
}

时间复杂度O(nlog2n)O(n\log^2 n)

文章目录
  1. 1. A
  2. 2. B
  3. 3. C
|

博客使用Disqus作为评论系统