前言
不平衡的一集
T1 动态数点
题意很清楚
我们先思考怎么暴力搞
如果一个数是 \(k\) 那么它一定是这个区间的最大公约数
可以直接搞个 ST表 加 二分 每次枚举左端点 由于 gcd 和 二分都有 \(\log\) 总时间复杂度 \(O(n\log^2 n)\)
然后就挂了 30pts(((
考虑优化成 \(O(n\log n)\)
考虑到枚举左端点实在是太亏了 不如枚举中间的 gcd 然后向左右扩充
考虑怎么找到左边第一个不是当前的数的倍数
可以参考并查集路径压缩那样子 通过上一个来转移即可
因为若 \(a_{l-1}\) 是 \(a_l\) 的倍数 那么 \(a_{l-1}\) 的倍数也是 \(a_l\) 的倍数 直接跳着访问即可
然后最终存起来左端点输出即可
时间复杂度 \(O(n\log n)\)
#include<bits/stdc++.h>
#pragma GCC optimize (1)
#pragma GCC optimize (2)
#pragma GCC optimize (3,"Ofast","inline")
#define N 500005
using namespace std;
int n,l[N],r[N],a[N];
int q[N],top,maxx;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
l[i]=i;
while(l[i]-1>=1&&a[l[i]-1]%a[i]==0) l[i]=l[l[i]-1];
}
for(int i=n;i>=1;i--)
{
r[i]=i;
while(r[i]+1<=n&&a[r[i]+1]%a[i]==0) r[i]=r[r[i]+1];
}
for(int i=1;i<=n;i++)
if(r[i]-l[i]>maxx) maxx=r[i]-l[i],top=1,q[top]=l[i];
else if(r[i]-l[i]==maxx) q[++top]=l[i];
sort(q+1,q+1+top);
int len=unique(q+1,q+1+top)-q-1;
printf("%d %d\n",len,maxx);
for(int i=1;i<=len;i++)
printf("%d ",q[i]);
return 0;
}
T2 中位数
\(n\leq 2000\space a_i \leq 2000\)
思考
这题过程堪称逆天
设 \(sum=(\sum\limits_{i=1}^n a_i)\),\(mid=sum/2\)
不妨思考一下 若随意选一个子集 它们的和为 \(x\)
那么一定存在它的 补集 和为 \(sum-x\)
很明显 若存在\(x\leq mid\) 那么 \(sum-x \ge mid\)
所以我们把问题丢到数轴上考虑
所以 它们是一一对应的
由于题目规定不能选空集 所以 \(mid\) 左边少了一个数
因此 \(mid\)右边第一个数就是子集的中位数
然后就是一个状态 \(01\) 背包
观察到只需记录 \(01\) 即可 所以用 \(bitset\) 优化即可
时间复杂度 \(O(\frac{nm^2}{w})\) 能过
#include<bits/stdc++.h>
#pragma GCC optimize (1)
#pragma GCC optimize (2)
#pragma GCC optimize (3,"Ofast","inline")
#define N 2005
#define ll long long
using namespace std;
int n,a[N],sum;
bitset<N*N> f;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),sum+=a[i];
f.set(0);
for(int i=1;i<=n;i++)
f|=(f<<a[i]);
for(int i=(sum+1)/2;i<=sum;i++)
if(f[i])
{
printf("%d",i);
break;
}
return 0;
}
T3 出题
\(n,q\leq 10^5\space d\leq 10^4\)
这是一道毒瘤题
题意：给你 \(q\) 个操作 保证在区间 \(1\to n\) 答案为所有 \(2\) 操作的和 现在每次会去掉一个操作 要求求出去掉操作后的操作答案
这题考虑去掉一个方案后会损失的答案值
如果暴力搞会很大 不如记录一下
不妨想一想，如果去掉一个操作后会失去什么贡献？分类一下
- 如果操作是 1 修改 失去的答案就要查找后面的 \(2\) 操作 且 \(2\) 操作删去时间要比当前 \(1\) 修改后
- 如果操作是 2 修改 失去的答案就要查找前面的 \(1\) 操作 且 \(1\) 操作删去时间要比当前 \(2\) 修改后
这样让我们回忆起一道题
这一题 不就是离线后 CDQ 分治优化三维偏序吗
这一道题，已经有了 编号 和 时间 两维
第三维发现是 \(l,r\) 的交集的多少
一个树状数组维护即可
时间复杂度 \(O(n\log^2n)\)
Code
#include<bits/stdc++.h>
#define N 200005
#define ll long long
using namespace std;
int n,m;
struct BIT{
ll tr[N],tr2[N];
void add(int x,ll v)
{
ll now=x;
while(x<=n+1)
{
tr[x]+=v;
tr2[x]+=now*v;
x+=x&-x;
}
}
ll ask(int x)
{
ll sum1=0,sum2=0,now=x;
while(x)
{
sum1+=tr[x];
sum2+=tr2[x];
x-=x&-x;
}
return sum1*(now+1)-sum2;
}
void clear(int x)
{
while(x<=n+1)
{
tr[x]=0;
tr2[x]=0;
x+=x&-x;
}
}
}tr;
int stk[2*N],top;
ll ans[N];
struct node{
int opr;
int id,tim,l,r;
ll d;
}q[N];
bool cmp1(node a,node b)
{
return a.tim>b.tim;
}
void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
solve(l,mid);
solve(mid+1,r);
sort(q+l,q+1+mid,cmp1);
sort(q+mid+1,q+1+r,cmp1);
int i=l,j=mid+1;
for(i=l;i<=mid;i++)
{
while(j<=r&&q[j].tim>q[i].tim)
{
if(q[j].opr==1)
{
j++;
continue;
}
tr.add(q[j].l,1);
tr.add(q[j].r+1,-1);
stk[++top]=q[j].l;
stk[++top]=q[j].r+1;
j++;
}
if(q[i].opr==1)
ans[q[i].tim]+=(tr.ask(q[i].r)-tr.ask(q[i].l-1))*q[i].d;
}
while(top)
tr.clear(stk[top--]);
i=l,j=mid+1;
for(j=mid+1;j<=r;j++)
{
while(i<=mid&&q[i].tim>q[j].tim)
{
if(q[i].opr==2)
{
i++;
continue;
}
tr.add(q[i].l,q[i].d);
tr.add(q[i].r+1,-q[i].d);
stk[++top]=q[i].l;
stk[++top]=q[i].r+1;
i++;
}
if(q[j].opr==2)
ans[q[j].tim]+=tr.ask(q[j].r)-tr.ask(q[j].l-1);
}
while(top)
tr.clear(stk[top--]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m-1;i++)
{
int x;
scanf("%d",&x);
q[x].tim=m-i;
}
for(int i=1;i<=m;i++)
{
if(q[i].tim==0) q[i].tim=m;
scanf("%d%d%d",&q[i].opr,&q[i].l,&q[i].r);
if(q[i].opr==1)
scanf("%lld",&q[i].d);
}
solve(1,m);
for(int i=m;i>=1;i--)
ans[i]+=ans[i+1];
for(int i=m;i>=1;i--)
printf("%lld\n",ans[i]);
return 0;
}