test20190629

Posted on | Views:

$\%\ nicodafagood$ .

$quadratic$

  • 给 $n$ 个二次项系数为 $1$ 的二次函数,分别求 $x=1\sim n$ 时这 $n$ 个函数中的最小值. $n\leq 10^5$ .
  • 因为二次项贡献固定,所以只需要算一次项和常数项的贡献,就相当于 $n$ 条直线在某个位置的最小值.
  • 用凸包或者李超线段树写一下就好了.
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e6+10;
int n;
int A[MAXN],B[MAXN];
ll k[MAXN],b[MAXN];
const ll inf=1e18;
inline ll calc(int seg,int x)
{
	return k[seg]*x+b[seg];
}
inline int sgn(ll x)
{
	if(!x)
		return 0;
	return x<0?-1:1;
}
ll ans;
struct SegTree
{
	int nodecnt;
	SegTree(){nodecnt=0;}
	struct node
	{
		int ls,rs,id;
		ll mi;
		node(){ls=rs=id=0;mi=inf;}
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[root.ls]
#define rson Tree[root.rs]
	void BuildTree(int l,int r)
	{
		int o=++nodecnt;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		root.ls=nodecnt+1;
		BuildTree(l,mid);
		root.rs=nodecnt+1;
		BuildTree(mid+1,r);
	}
	void pushup(int o,int l,int r)
	{
		if(root.id)
			root.mi=k[root.id]<0?calc(root.id,r):calc(root.id,l);
		else
			root.mi=inf;
		if(l<r)
		{
			root.mi=min(root.mi,lson.mi);
			root.mi=min(root.mi,rson.mi);
		}
	}
	void upd(int o,int l,int r,int L,int R,int seg)
	{
		if(L<=l && r<=R)
		{
			if(!root.id)
			{
				root.id=seg;
				pushup(o,l,r);
				return;
			}
			bool f1=calc(root.id,l)<calc(seg,l);
			bool f2=calc(root.id,r)<calc(seg,r);
			if(f1==f2 || l==r)
			{
				if(!f1)
				{
					root.id=seg;
					pushup(o,l,r);	
				}
				return;
			}
			int mid=(l+r)>>1;
			bool f3=calc(root.id,mid)<calc(seg,mid);
			if(f1==f3)
			{
				if(f1)
					upd(root.rs,mid+1,r,L,R,seg);
				else
					upd(root.rs,mid+1,r,L,R,root.id),root.id=seg;
			}
			else
			{
				if(f1)
					upd(root.ls,l,mid,L,R,root.id),root.id=seg;
				else
					upd(root.ls,l,mid,L,R,seg);
			}
		}
		else
		{
			int mid=(l+r)>>1;
			if(L<=mid)
				upd(root.ls,l,mid,L,R,seg);
			if(R>mid)
				upd(root.rs,mid+1,r,L,R,seg);
		}
		pushup(o,l,r);
	}
	void query(int o,int l,int r,int pos)
	{
		if(root.id)
		{
			if(k[root.id]<0)
				ans=min(ans,calc(root.id,min(r,pos)));
			else
				ans=min(ans,calc(root.id,max(l,pos)));
		}
		if(l==r)
		{
			ans=min(ans,root.mi);
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)
			query(root.ls,l,mid,pos);
		else
			query(root.rs,mid+1,r,pos);
	}
}T;
int main()
{
	freopen("quadratic.in","r",stdin);
	freopen("quadratic.out","w",stdout);
	n=read();
	b[0]=inf;
	for(int i=1;i<=n;++i)
		A[i]=read();
	T.BuildTree(1,n);
	for(int i=1;i<=n;++i)
	{
		B[i]=read();
		k[i]=-2LL*A[i];
		b[i]=1LL*A[i]*A[i]+B[i];
		T.upd(1,1,n,1,n,i);
	}
	for(int i=1;i<=n;++i)
	{
		ans=inf;
		T.query(1,1,n,i);
		printf("%lld\n",ans+1LL*i*i);
	}
	return 0;
}

$equation$

  • 给定 $a,b,p,x$ ,求解 $[1,x]$ 中,满足 $n\cdot a^n\equiv b \mod p$ 的 $n$ 的数目.
  • $0\leq a,b<p\leq 10^6.x\leq 10^{12}.$ 保证 $p$ 为质数.
  • 根据费马小定理,指数可以对 $p-1$ 取模.而 $p$ 的范围比较小,于是直接枚举 $n$ 对 $p-1$ 取模的结果 $i$.
  • 即,在 $[0,p-2]$ 内枚举 $i$ ,对应贡献为满足下面两个条件的 $n$ 的数目.

$$
n\equiv i (mod\ p-1),n\equiv b\cdot a^{-i}(mod\ p)
$$

  • 用 $CRT$ 求解 $p\cdot (p-1)$ 内的 $n$ ,再计算 $[1,x]$ 内对应 $n$ 数目即可.
  • 时间复杂度 $O(p\cdot logp)$ .

$datastructure$

  • 给定一个长度为 $n$ 的正整数数列 $a$ ,要求支持下列操作,共 $m$ 次.
  1. 将区间 $[l,r]$ 内的元素加上 $x$ .
  2. 将区间 $[l,r]$ 内的元素开平方,向下取整.
  3. 询问区间 $[l,r]$ 内的元素平方总和.
  4. 询问区间 $[l,r]$ 内的元素总和.
  • $n,m\leq 10^5,1\leq a_i,x\leq 10^9$ .
  • 考虑用线段树维护询问的答案.
  • 有一档部分分是没有操作 $1$ 的,可以直接做,对每个区间记录元素是否都是 $1$ ,开方时讨论即可.
  • 正解做法类似,不过优化的方法不同.开方 $[l,r]$ 时,先询问 $[l,r]$ 内的最大值 $a$ 与最小值 $b$ .
  • 开方时都向下取整,若 $\sqrt {a}=\sqrt {b}$ ,就将这个区间全部修改为 $\sqrt a$ .若 $a-\sqrt a=b-\sqrt b$ ,就给这个区间全部减去 $a-\sqrt a$ ,因为这个差是关于元素大小不下降的.
  • 若两种情况都不满足,就暴力修改区间内所有元素.
  • 因为一次区间加最多会使得 $logn$ 个结点的 $a-b$ 变化,而变化后我们最多暴力开 $6$ 次方它就变成 $1$ 了,所以操作 $1,2$ 复杂度均摊下来,一次为 $O(logn)$ .于是总时间复杂度 $O(nlogn)$ .

$unsigned\ long\ long$ 输出指令是 $\%llu$ .考试写成 $\%u$ 了. $70\to 15$ .