2021.08.28 膜你赛
lock
Description
LYK 想把你的智商锁起来，它出了道神题。
它有一壶水，这壶水的水量在[L,R]中，你只知道 L 和 R 是多少，但你并不知道具体的值是多少。它有两个容量为无穷大的杯子。它想尽可能把壶里的水均匀的分在两个杯子中。它觉得
这个任务可能太难了，因此它只要求最终两个杯子的水的容量至多相差 1。并且它也不要求
把壶里的水全部倒完，只要求最终剩在壶里的水不超过 1。LYK 在倒水过程中，不知道这壶水还有多少水，但能知道是否倒完了。
一个最笨的方法是左边倒 1 滴，右边的倒 1 滴，左边再倒 1 滴，这样依次下去，直到壶
里没水或者已经倒了 R-1 的水时，就满足条件了。但根据题名，这题并不简单。
LYK 想知道如果采用最优策略，则在最坏情况下 LYK 要倒多少次水才能满足条件。
（注：最优策略下的最坏情况指，事件总是往最坏的情况发展，例如 L=2,R=10000，你
第一次就大胆的往第一杯水倒 2 滴水，但可能壶里一开始总共就只有 2 的水，就不满足条件
了。所以你的方案应当是就算情况再坏，也能满足条件，并且在此基础上倒水的次数最少）
Solution
手模样例，大力找规律，发现如果固定 \(r\) ，\(l\) 递减的话，答案也会减小，几乎是每隔两个数答案+1，因此直接推出式子，Ans=(r-l+2)/2 ,然后还要特判几种情况，然后有一种情况没有判，但是数据没有这种情况，然后就过了。
Code
/*
* @Author: smyslenny
* @Date: 2021.08.
* @Title:
* @Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#define int long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)
using namespace std;
const int mod=998244353;
const int M=1e3+5;
int l,r;
int read()
{
int x=0,y=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
namespace substack1{
int mp[6][6]={{0,0,0,0,0,0},
{0,0,1,2,2,3},
{0,0,1,2,2,2},
{0,0,0,2,2,2},
{0,0,0,0,2,2},
{0,0,0,0,0,2}};
void main()
{
printf("%lld\n",mp[l][r]);
}
}
namespace substack2{
int Ans;
void main()
{
Ans=2;
if(l>r) printf("0\n");
else if(r<=1) printf("0\n");
else if(r<=2)
printf("1\n");
else if(l==r)
printf("2\n");
else
{
printf("%lld\n",max(2ll,(r-l+2ll)/2ll));
}
}
}
signed main()
{
// freopen("lock.in","r",stdin);
// freopen("lock.out","w",stdout);
l=read(),r=read();
if(r<=5) substack1::main();
else substack2::main();
return 0;
}
sequence
Description
LYK 有一个序列，它想玩一个游戏，就是找一段最长的连续的数字，使得它们的和小于等于 p，我们假设这个最长的区间的长度为 L。
但这件事好像有点简单，因此 LYK 给自己一次机会：将其中一段连续的长度不超过 d 的区间的数都变成 0，之后再找最长的连续的数字使得和小于等于 p。
LYK 想知道，在所有的可能的改变策略中，L 最大为多少。
Solution
预处理出所有 d 区间的答案，然后用单调队列维护 d 的最大答案，双指针求最大区间。
Code
/*
* @Author: smyslenny
* @Date: 2021.08.
* @Title:
* @Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#define int long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)
using namespace std;
const int mod=998244353;
const int M=1e6+5;
int n,p,d,l,Ans,Div[M];
int read()//
{
int x=0,y=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
int Max,js,mp[M],sum[M],q[M],head=1,tail;
signed main()
{
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
n=read(),p=read(),d=read();
for(int i=1;i<=n;i++)
mp[i]=read(),sum[i]=sum[i-1]+mp[i];
for(int i=1;i<=n;i++)
Div[i]=sum[i]-sum[max(0ll,i-d)];//当前位置到 d 的和
for(int r=1;r<=n;r++)
{
while(Div[q[tail]]<=Div[r] && head<=tail) tail--;//当前点往前比当前点 d 的值要小的最远距离
q[++tail]=r;
while(sum[r]-sum[l]-Div[q[head]]>p && l<r)//删去之后找能到达的最远的位置
{
l++;//所能到达的最远左端点
while(head<=tail && q[head] <l+d) head++;//d 区间断向左挪
}
if(sum[r]-sum[l]-Div[q[head]]<=p)
Ans=max(Ans,r-l);
}
printf("%lld\n",Ans);
return 0;
}
fight
Description
\(LYK\) 有 \(n\) 个小朋友排成一排。第 \(i\) 个小朋友的战斗力是 \(a_i\)，且他们的战斗力互不相同。
战斗力高的会打败战斗力低的。
\(LYK\) 想恶搞这些小朋友们，具体地，它有 \(k\) 次操作。
第 \(i\) 次操作会有两个参数 \(l_i\) 和 \(r_i\)，表示如果两个小朋友 \(A\)，\(B\) 的战斗力均在 \([l_i,r_i]\) 这
段区间中，它们的打架结果会相反。即如果一开始 \(A\) 能赢 \(B\)，则现在变成 \(B\) 能赢 \(A\)。当然它
们的打架结果可能在后来的操作中又被反过来。
\(LYK\) 想知道，\(k\) 次操作后，存在多少三元组 \((a,b,c)\)，其中 \(a\) 能赢 \(b\)，\(b\) 能赢 \(c\)，\(c\) 能赢 \(a\)。
注意这里 \((a,b,c),(b,c,a),(c,a,b)\) 算同一种三元组。
Solution
先离散化，答案是用 C(n,3)-不合法的；
不合法的三元组必定有一个可以战胜其他两个，那么只要统计出他能打败的人，再C(cnt,2)，再求一下和。线段树维护修改查询操作，又发现对于i来说只有覆盖i的修改才对i有用，所以对于所有操作只要扫两遍即可
Code
/*
* @Author: smyslenny
* @Date: 2021.08.
* @Title:
* @Main idea:
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#define ll long long
#define INF 0x3f3f3f3f
#define orz cout<<"LKP AK IOI\n"
#define MAX(a,b) (a)>(b)?(a):(b)
#define MIN(a,b) (a)>(b)?(a):(b)
#define lson(x) (x)<<1
#define rson(x) (x)<<1|1
using namespace std;
const int mod=998244353;
const int M=1e3+5;
int n,k,mp[M],Ans;
pair<int,int> a[M],b[M];
int read()
{
int x=0,y=1;
char c=getchar();
while(c<'0' || c>'9') {if(c=='-') y=0;c=getchar();}
while(c>='0' && c<='9') { x=x*10+(c^48);c=getchar();}
return y?x:-x;
}
struct tr
{
int l,r,mid,len,sum,laz;
}tree[M<<2];
void buildtree(int p,int l,int r)
{
tree[p].l=r,tree[p].r=r,tree[p].mid=(l+r)>>1,tree[p].len=r-l+1;
if(l==r) return;
int mid=(l+r)>>1;
buildtree(lson(p),l,mid);
buildtree(rson(p),mid+1,r);
}
void push_down(int p)
{
tree[lson(p)].sum=tree[lson(p)].len-tree[lson(p)].sum;
tree[rson(p)].sum=tree[rson(p)].len-tree[rson(p)].sum;
tree[lson(p)].laz^=1;tree[rson(p)].laz^=1;
tree[p].laz=0;
}
void update(int p,int l,int r)
{
if(l<=tree[p].l && tree[p].r<=r)
{
tree[p].sum=tree[p].len-tree[p].sum;
tree[p].laz^=1;
return;
}
if(tree[p].laz) push_down(p);
if(l<=tree[p].mid) update(lson(p),l,tree[p].mid);
if(r>=tree[p].mid) update(rson(p),tree[p].mid+1,r);
tree[p].sum=tree[lson(p)].sum+tree[rson(p)].sum;
}
int query(int p,int l,int r,int op)
{
if(l>r) return 0;
if(l<=tree[p].l && r>=tree[p].r) return op?tree[p].sum:tree[p].len-tree[p].sum;
if(tree[p].laz) push_down(p);
if(l<=tree[p].mid)
if(r<tree[p].mid) return query(lson(p),l,r,op)+query(rson(p),l,r,op);
else return query(lson(p),l,r,op);
else return query(rson(p),l,r,op);
}
int main()
{
n=read(),k=read();
for(int i=1;i<=n;i++) mp[i]=read();sort(mp+1,mp+1+n);
sort(mp+1,mp+1+n);
buildtree(1,1,n);
Ans=n*(n-1)*(n-2)/6;
int x=unique(mp+1,mp+1+n)-mp-1;
for(int i=1;i<=k;i++)
{
int l=read(),r=read();
l=lower_bound(mp+1,mp+1+x,l)-mp;
r=upper_bound(mp+1,mp+1+x,r)-mp-1;
a[i]=make_pair(l,r),b[i]=make_pair(r,l);
}
for(int i=1,j=1,y=1;i<=n;i++)
{
while(j<=y && a[j].first==i)
update(1,a[j].first,a[j].second),++j;
int x=query(1,1,i-1,0)+query(1,i+1,n,1);
Ans-=x*(x-1)/2;
while(y<=k&&b[y].first==i)
update(1,b[y].second,b[y].first),++k;
}
printf("%d\n",Ans);
return 0;
}