Solutions
A：Equivalent Prefixes
题意：
若$\text{RMQ(u,l,r)=RMQ(v,l,r)}$ for all $1{\leq}l{\leq}r{\leq}m$，则为$equivalent$
其中$\text{RMQ(w,l,r)}$的定义是${[l,r]}$区间内最小数的下标
给两个数组，每组元素各不相同，求最大的$p{\leq}n\ where\ \{a_1,a_2,{\ldots}a_p\} are\ equivalent$
单调栈思路：
处理出每一位左边第一个比它小的下标，然后相同的话可取，不同不可取。
假如当前处理$a_i$，(也就是$\{a_1,a_2,{\ldots}a_{i-1}\}$满足条件)，假设比它第一个小的是$last[i]$，那么$last[i]$右边的$RMQ$一定是$a_i$，这样的话，$last[i]$左边的$RMQ$一定与新数无关，因为仅仅$last[i]$处就已经比$a_i$小了。
可以利用单调栈求每一位左边第一个比它小的下标
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e5+10;
4
5 int n,a[maxn],b[maxn],ida[maxn],idb[maxn];
6
7 stack<pair<int,int> > s;
8
9 int main() {
10 while(~scanf("%d",&n)) {
11 s.push(make_pair(-1,-1));
12 for(int i=0;i<n;i++) {
13 scanf("%d",&a[i]);
14 while(!s.empty()&&s.top().first>a[i]) s.pop();
15 ida[i]=s.top().second;
16 s.push(make_pair(a[i],i));
17 }
18 while(!s.empty()) s.pop();
19 s.push(make_pair(-1,-1));
20 for(int i=0;i<n;i++) {
21 scanf("%d",&b[i]);
22 while(!s.empty()&&s.top().first>b[i]) s.pop();
23 idb[i]=s.top().second;
24 s.push(make_pair(b[i],i));
25 }
26 int cur=0;
27 while(cur<n) {
28 if(ida[cur]==idb[cur]) cur++;
29 else break;
30 }
31 printf("%d\n",cur);
32 }
33 return 0;
34 }
二分+分治+ST思路：
通过$ST$表预处理出$RMQ$，$p$具有单调性，可以二分判断是否满足条件，然后询问$1{\sim}mid$最小值，再分治
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=100010;
4
5 int dpa[maxn][20],dpb[maxn][20],a[maxn],b[maxn];
6 int mm[maxn],n,ida[maxn],idb[maxn];
7
8 void init() {
9 mm[0]=-1;
10 for(int i=1;i<=n;i++) {
11 mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
12 dpa[i][0]=a[i];
13 dpb[i][0]=b[i];
14 }
15 for(int j=1;j<=mm[n];j++) {
16 for(int i=1;i+(1<<j)-1<=n;i++) {
17 dpa[i][j]=min(dpa[i][j-1],dpa[i+(1<<(j-1))][j-1]);
18 dpb[i][j]=min(dpb[i][j-1],dpb[i+(1<<(j-1))][j-1]);
19 }
20 }
21 }
22
23 int rmqa(int x,int y) {
24 int k=mm[y-x+1];
25 return ida[min(dpa[x][k],dpa[y-(1<<k)+1][k])];
26 }
27
28 int rmqb(int x,int y) {
29 int k=mm[y-x+1];
30 return idb[min(dpb[x][k],dpb[y-(1<<k)+1][k])];
31 }
32
33 bool dfs(int l,int r) {
34 if(l>=r) return true;
35 int x=rmqa(l,r);
36 int y=rmqb(l,r);
37 if(x!=y) return false;
38 else return dfs(1,x-1)&&dfs(y+1,r);
39 }
40
41 bool check(int mid) {
42 return dfs(1,mid);
43 }
44
45 int main() {
46 while(~scanf("%d",&n)) {
47 for(int i=1;i<=n;i++) {
48 scanf("%d",&a[i]);
49 ida[a[i]]=i;
50 }
51 for(int i=1;i<=n;i++) {
52 scanf("%d",&b[i]);
53 idb[b[i]]=i;
54 }
55 init();
56 int l=1,r=n,ans=1;
57 while(l<=r) {
58 int mid=(l+r)>>1;
59 if(check(mid)) {
60 ans=mid;
61 l=mid+1;
62 } else {
63 r=mid-1;
64 }
65 }
66 printf("%d\n",ans);
67 }
68 }
B: Integration
题意：
给出$n$个数，$a_1,a_2,\ldots,a_n$，求$\frac1\pi\int_0^{\infty}\frac1{\prod_{i=0}^n(a_i^2+x^2)}dx$
因为分母是连乘积，所以可以列项拆分。推几项可以得出规律
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1010;
4 typedef long long ll;
5 const int mod=1e9+7;
6
7 ll a[maxn];
8 int n;
9
10 ll q_power(ll a,ll b) {
11 ll ans=1,tmp=a%mod;
12 while(b) {
13 if(b&1) ans=ans*tmp%mod;
14 tmp=tmp*tmp%mod;
15 b>>=1;
16 }
17 return ans;
18 }
19
20 int main() {
21 while(~scanf("%d",&n)) {
22 for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
23 ll ans=0;
24 for(int i=1;i<=n;i++) {
25 ll tmp=1;
26 for(int j=1;j<=n;j++) {
27 if(i==j) continue;
28 tmp=tmp*(((a[j]*a[j]%mod)-(a[i]*a[i]%mod)+mod)%mod)%mod;
29 }
30 tmp=tmp*2*a[i]%mod;
31 ans=(ans+q_power(tmp,mod-2))%mod;
32 }
33 printf("%lld\n",ans);
34 }
35 }
C：Euclidean Distance
题意：
给出$A$点的$n$维坐标$A=(a_1/m,a_2/m,\ldots,a_n/m)$，请找一点$P=(p_1,p_2,\ldots,p_n)$，满足一下条件
- $p_1,p_2,\ldots,p_n\ \in{\mathbb{R}}$
- $p_1,p_2,\ldots,p_n{\geq}0$
- $p_1+p_2+\ldots+p_n=1$
使得$\sum_{i=1}^n(a_i/m-p_i)^2$最小。
思路：
首先，我们可以将$p$的坐标放大m倍,那么答案可以转化为：
$\sum_{i=1}^n(a_i/m-p_i)^2\ =\ \sum_{i=1}^n[m(a_i/m-p_i)]^2\ \Rightarrow\ \frac1{m^2}\sum_{i=1}^n(a_i-mpi)^2$
考虑$a_i$为每个矩形的高，减去的$m$相当于削减矩形的高度，首先将$a_1,a_2,\ldots,a_n$降序排列。证：
削减高度较大的收益会比削减高度较小的收益更大，（比如负数，减去数反而变大了）。
如图中的绿线，把矩形一点一点往下推，然后下一步一起推，道理同上。
若不能进一步往下推，就把整体减一点点。可以预处理出前缀和。然后判断够不够把$a_i$前面的全部推平。
具体细节可以见上面大佬的博客。
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define ll long long
4 int n,m,a[10010],sum[10010];
5
6 bool cmp(int a,int b) {
7 return a>b;
8 }
9
10 int main() {
11 while(~scanf("%d%d",&n,&m)) {
12 for(int i=1;i<=n;i++) scanf("%d",&a[i]);
13 sort(a+1,a+n+1,cmp);
14 sum[0]=-m;
15 for(int i=1;i<=n;i++) {
16 sum[i]=sum[i-1]+a[i];
17 }
18 ll frac1,frac2;
19 int now=n;
20 for(int i=1;i<n;i++) {
21 if(sum[i]>a[i+1]*i) {
22 now=i;
23 break;
24 }
25 }
26 frac1=1ll*sum[now]*sum[now]*now;
27 frac2=now*now;
28 for(int i=now+1;i<=n;i++) {
29 frac1+=1ll*a[i]*a[i]*frac2;
30 }
31 frac2=frac2*1ll*m*m;
32 ll tmp=__gcd(frac1,frac2);
33 if(frac2/tmp==1) printf("%lld\n",frac1/tmp);
34 else if(!(frac1/tmp)) printf("0\n");
35 else printf("%lld/%lld\n",frac1/tmp,frac2/tmp);
36 }
37 }
E：ABBA
题意：
给出$2(n+m)$个$A,B$构成序列，求可以划分为$n$个$AB$，$m$个$BA$的序列的个数。
思路：
首先贪心的想，前$n$个$A$是$AB$的$A$，前$m$个$B$是$BA$的$B$。
然后$dp[i][j]$表示放了$i$个$A$，$j$个$B$的方案数。
若$i{\leq}n$，$A$可以直接放
若$j{\leq}m$，$B$可以直接放
若$i-n{\leq}j$，即现在用于组合$BA$的$A$的数量小于$B$的数量，$A$可以放
若$j-m{\leq}i$，即现在用于组合$AB$的$B$的数量小于$A$的数量，$B$可以放
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int mod=1e9+7;
4
5 int dp[2010][2010];
6 int n,m;
7
8 int main() {
9 while(~scanf("%d%d",&n,&m)) {
10 for(int i=0;i<=n+m;i++) {
11 for(int j=0;j<=n+m;j++)
12 dp[i][j]=0;
13 }
14 dp[0][0]=1;
15 for(int i=0;i<=n+m;i++) {
16 for(int j=0;j<=n+m;j++) {
17 if(i-n<j) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
18 if(j-m<i) dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
19 }
20 }
21 printf("%d\n",dp[n+m][n+m]);
22 }
23 }
F：Random Point in Triangle
题意：
给出三角形三点坐标$A,B,C$，求
$$E=max\{S_{PAB},S_{PBC},S_{PCA}\}$$
输出$36{\times}E$
思路：
暂时只知道$ans=22{\times}S_{ABC}$，证明不会，记一下叉积求面积。$S_{ABC}=\frac12\vec{AB}{\times}\vec{AC}$
1 #include<iostream>
2 #include<cstdio>
3 #define lowbit(x) (x&(-x))
4 #include<cstring>
5 using namespace std;
6 typedef long long ll;
7
8 int main() {
9 ll x1,y1,x2,y2,x3,y3;
10 while(~scanf("%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3)) {
11 ll ans=abs(x2*y3-x2*y1-x1*y3-y2*x3+x1*y2+y1*x3);
12 printf("%lld\n",22/2*ans);
13 }
14 }
I：Points Division
题意：
给出$n$个点，每个点有两个权值$a_i,b_i$，然后把这些点划分为两个集合，若点$i$在$A$中，则贡献为$a_i$，若若点$i$在$B$中，则贡献为$b_i$，
要求集合$A$在集合$B$的左上方。求划分后的最大权值和。
思路：
显然可以用一条递增的折线划分为两个区域。然后就开始玄学了。
$dp[i]$表示第$i$个点在折线上时的最大权值和。
当加入$i$时，如果$y_i$大于之前的$y_j$，则$i$的贡献为$a_i$，如果$y_i$小于之前的$y_j$，则$i$的贡献为$b_i$
那么$dp[j]=
\begin{cases}
dp[j]+b_i & j<i,y_j>y_i\\
dp[j]+a_i & j<i,y_j<y_i
\end{cases}$
$dp[i]=b_i+max_{1{\leq}<i,y_j<y_i}dp[j]$
式子可以用线段树维护区间最值（但是我比较迷，看不太懂）
还需要多加一个点。因为dp初始化为0。
（仅复习下线段树区间修改时的最大值，注意可能L>R，所以判一下）
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn=1e5+10;
4 typedef long long ll;
5 const int inf=0x3f3f3f3f;
6
7 struct node{
8 ll x,y,a,b;
9 }p[maxn];
10 ll t[maxn];
11 int tot,cnt,n;
12
13 bool cmp(node a,node b) {
14 if(a.x==b.x) return a.y>b.y;
15 else return a.x<b.x;
16 }
17
18 ll maxx[maxn<<2],lazy[maxn<<2];
19
20 void pushup(int rt) {
21 maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
22 }
23
24 void build(int l,int r,int rt) {
25 lazy[rt]=maxx[rt]=0;
26 if(l==r) return ;
27 int mid=(l+r)>>1;
28 build(l,mid,rt<<1);
29 build(mid+1,r,rt<<1|1);
30 pushup(rt);
31 }
32
33 void pushdown(int rt) {
34 if(lazy[rt]) {
35 lazy[rt<<1]+=lazy[rt];
36 lazy[rt<<1|1]+=lazy[rt];
37 maxx[rt<<1]+=lazy[rt];
38 maxx[rt<<1|1]+=lazy[rt];
39 lazy[rt]=0;
40 }
41 }
42
43 void updata1(int pos,ll val,int l,int r,int rt) {
44 if(l==r) {
45 maxx[rt]=max(maxx[rt],val);
46 return ;
47 }
48 int mid=(l+r)>>1;
49 pushdown(rt);
50 if(pos<=mid) updata1(pos,val,l,mid,rt<<1);
51 else updata1(pos,val,mid+1,r,rt<<1|1);
52 pushup(rt);
53 }
54
55 void updata2(int L,int R,int val,int l,int r,int rt) {
56 if(L<=l&&R>=r) {
57 maxx[rt]+=val;
58 lazy[rt]+=val;
59 return ;
60 }
61 int mid=(l+r)>>1;
62 pushdown(rt);
63 if(L<=mid) updata2(L,R,val,l,mid,rt<<1);
64 if(R>mid) updata2(L,R,val,mid+1,r,rt<<1|1);
65 pushup(rt);
66 }
67
68 ll query(int L,int R,int l,int r,int rt) {
69 if(L<=l&&R>=r) {
70 return maxx[rt];
71 }
72 ll ans=0;
73 int mid=(l+r)>>1;
74 pushdown(rt);
75 if(L<=mid) ans=max(ans,query(L,R,l,mid,rt<<1));
76 if(R>mid) ans=max(ans,query(L,R,mid+1,r,rt<<1|1));
77 return ans;
78 }
79
80 int main() {
81 while(~scanf("%d",&n)) {
82 cnt=0;
83 for(int i=1;i<=n;i++) {
84 scanf("%lld%lld%lld%lld",&p[i].x,&p[i].y,&p[i].a,&p[i].b);
85 t[++cnt]=p[i].y;
86 }
87 sort(p+1,p+n+1,cmp);
88 sort(t+1,t+cnt+1);
89 tot=unique(t+1,t+cnt+1)-t-1;
90 for(int i=1;i<=n;i++) {
91 p[i].y=lower_bound(t+1,t+tot+1,p[i].y)-t+1;
92 }
93 tot++;
94 build(1,tot,1);
95 for(int i=1;i<=n;i++) {
96 ll ans=query(1,p[i].y,1,tot,1);
97 updata1(p[i].y,ans+p[i].b,1,tot,1);
98 updata2(1,p[i].y-1,p[i].a,1,tot,1);
99 if(p[i].y+1<=tot) updata2(p[i].y+1,tot,p[i].b,1,tot,1);
100 }
101 printf("%lld\n",maxx[1]);
102 }
103 }
J：Fraction Comparision
题意：
判断$\frac{x}a$与$\frac{y}b$的大小关系
- $0{\leq}x,y{\leq}10^{18}$
- $1{\leq}a,b{\leq}10^9$
思路：
不能用浮点数判断(精度不够？)
把$\frac{x}a$写成${\lfloor}{\frac{x}a}{\rfloor}+{x\%a}$ 先比较整数部分，再交叉相乘比较分数
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 void out(ll x,ll y) { 6 if(x==y) puts("="); 7 else if(x>y) puts(">"); 8 else puts("<"); 9 } 10 11 12 int main() { 13 ll x,a,y,b; 14 while(~scanf("%lld%lld%lld%lld",&x,&a,&y,&b)) { 15 ll A=x/a; 16 ll B=y/b; 17 x%=a; 18 y%=b; 19 if(A!=B) out(A,B); 20 else out(xb,ya); 21 } 22 return 0; 23 }
