7.3总结
得分情况
估分:60+40+100=200
实际:60+40+30=130
Rank 9
萎的一批
好歹把T1T2的暴力分拿满了
T1
比赛的时候想了很久没有思路，就打暴力把人一个个塞进去，拿了暴力分60分
正解：
操作一：
首先，放人进去的时候，优先级是固定的。所以我们可以用后序遍历把优先级搞出来，用一个堆来维护哪些位置是空的，每次放人的时候就从堆里面找一个位置，删人的时候放一个位置进堆里面。(用线段树也可以搞，我就是用线段树打的)
操作二：
我们已经知道哪些点有人，那么把一个人删去时，就用倍增找到他最上面一个有人的节点，把它删去就好了。(用树链剖分也可以搞，cgh打了树剖)
T2
比赛的时候想了很久也没什么思路，就把40分暴力分给拿到了。
正解
首先考虑一种暴力：设f[i][0/1]表示前面的数与i进行位运算，结果的最大值和方案数。这样子做插入是O((2^{16}))的,询问是O(1)的。
怎么平衡一下插入和询问的时间复杂度呢？
运用广义平衡规划的思想，类似折半搜索一样，设f[i][j][0/1]表示前面的数中，前八位为i,与某个后八位为j的数进行位运算，后八位结果的最大值和方案数。
这样一来，插入时i是固定的，我们只用枚举j来更新f；而询问时j是固定的，只用枚举i来更新ans。
~好巧妙的思想啊~
T3
谴责出题人，暴力随便水过。
我以为它是满足二分性的，结果又TLE有WA爆炸了。
早知道就打暴力算了。
正解
首先，把读入的串分段，同一段里面满足每个数%d都是同一个值
由于不能有重复的数，所以要求一个maright[l]来表示最大右端点使a[l~maright[l]]中没有相同的数。
用哈希或map随便搞搞就好了
然后(n^2)暴力就切了哈哈
那么为了避免负数等情况，我们处理一下数据。对于一段每个数a[x]，令a[x]=(a[x]-min)/d+1，min即为这一段的最小值。
当l,r为左右端点时，满足(max{a_{l...r}}-min{a_{l...r}}+1leq r-l+1+k)即可更新答案。
考虑枚举左端点，找最大的右端点
设ma[r]表示当左端点为l时的(max{a_{l...r}}),mi[r]表示当左端点为l时的(min{a_{l...r}})
化一下式子变成(ma[r]-mi[r]-rleq k-l)，右边只与l有关。
设(b[r]=ma[r]-mi[r]-r),用线段树维护b,那么只用找出最大的r使(b[r]leq k-l)且r<=maright[l]
倒着枚举l，这样每一个ma[r]和mi[r]就只会单调上升或下降。其实ma与mi两个数组本身也是从左到右单调的。
那么当我们把l-1时，从l往后某一段ma就会由 一个小于a[l-1]的数 变为a[l-1]。但是我们不能直接用区间赋值，因为那样的话，由于那一段区间的ma[r]和mi[r]可能不同，所以没法更新区间b[r]的最小值。但是用区间加法就可以了。所以要打两个单调栈维护相同的一块块ma[r]和mi[r]。如果这个区间的ma[r]都相同（其实就等于a[r]）且小于a[l]，更新标记的时候给这个区间加上a[l]-ma[r]；如果这个区间的mi[r]（其实就等于a[r]）都相同且大于a[l]，更新标记的时候给这个区间加上mi[r]-a[l]。//这个地方打反了正负号调了一个小时。
由于线段树里面我们维护的是b[r]的最小值，所以最后用线段树的区间查询找l~n里面最靠右的满足b[r](leq)k-l并且r<=maright[l]的点就是以l为左端点的答案。
（这几天做过的最难的题目）
（其实也没多难，暴力就切了嘛233）
//for the moon
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 19260817
using namespace std;
struct qy
{
int mi,add;
};
int n,k,d,i,j,st,en,t;
int a[200005],maright[200005];
int ans1,ans2;
int hash[mod+5];
int ma[200005],mi[200005];
int z1[200005],z2[200005];
qy tree[800005];
void pushdown(int k,int l,int r)
{
if (l!=r)
{
tree[k*2].add+=tree[k].add;
tree[k*2+1].add+=tree[k].add;
tree[k*2].mi+=tree[k].add;
tree[k*2+1].mi+=tree[k].add;
}
tree[k].add=0;
}
void update(int k,int l,int r)
{
tree[k].mi=2100000000;
int mid=(l+r)/2;
if (l<=mid) tree[k].mi=min(tree[k].mi,tree[k*2].mi);
if (mid+1<=r)
tree[k].mi=min(tree[k].mi,tree[k*2+1].mi);
}
void insert(int k,int l,int r,int x)
{
pushdown(k,l,r);
if (l==r)
{
tree[k].add=0;
tree[k].mi+=-x;
}
else
{
int mid=(l+r)/2;
if (x<=mid) insert(k*2,l,mid,x);
else insert(k*2+1,mid+1,r,x);
update(k,l,r);
}
}
void add(int k,int l,int r,int x,int y,int z)
{
pushdown(k,l,r);
if ((l<=y)&&(r>=x))
{
if ((l>=x)&&(r<=y))
{
tree[k].add+=z;
tree[k].mi+=z;
return;
}
int mid=(l+r)/2;
add(k*2,l,mid,x,y,z);
add(k*2+1,mid+1,r,x,y,z);
update(k,l,r);
}
}
int query(int k,int l,int r,int x,int y,int z)
{
pushdown(k,l,r);
if ((l<=y)&&(r>=x))
{
int mid=(l+r)/2;
if ((l>=x)&&(r<=y))
{
if (l==r) return l;
else
{
if (tree[k*2+1].mi<=z) return query(k*2+1,mid+1,r,x,y,z);
else return query(k*2,l,mid,x,y,z);
}
}
int tt=0;
if (tree[k*2+1].mi<=z)
tt=query(k*2+1,mid+1,r,x,y,z);
if (tt!=0) return tt;
else return query(k*2,l,mid,x,y,z);
}
else
return 0;
}
void clear(int k,int l,int r)
{
tree[k].mi=tree[k].add=0;
int mid=(l+r)/2;
if (l!=r)
{
clear(k*2,l,mid);
clear(k*2+1,mid+1,r);
}
}
void does(int st,int en)
{
int mii=2000000000;
int l,r,ll,rr;
for (i=st;i<=en;i++)
mii=min(mii,a[i]);
for (i=st;i<=en;i++)
a[i]=(a[i]-mii)/d+1;
z1[0]=z2[0]=0;
for (l=en;l>=st;l--)
{
ma[l]=mi[l]=a[l];
insert(1,st,en,l);
while ((z1[0]>=1)&&(a[z1[z1[0]]]<=a[l]))
{
ll=z1[z1[0]];
rr=z1[z1[0]-1]-1;
if (z1[0]==1) rr=en;
add(1,st,en,ll,rr,a[l]-a[ll]);
z1[0]--;
}
z1[++z1[0]]=l;
while ((z2[0]>=1)&&(a[z2[z2[0]]]>=a[l]))
{
ll=z2[z2[0]];
rr=z2[z2[0]-1]-1;
if (z2[0]==1) rr=en;
add(1,st,en,ll,rr,a[ll]-a[l]);
z2[0]--;
}
z2[++z2[0]]=l;
r=query(1,st,en,l,maright[l],k-l);
if (r-l>=ans2-ans1)
{
ans1=l;
ans2=r;
}
}
clear(1,st,en);
}
int js(long long x)
{
return (long long)x%mod*x%mod;
}
int main()
{
freopen("read.in","r",stdin);
scanf("%d%d%d",&n,&k,&d);
for (i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]=a[i]+1000000000;
}
maright[n]=n;
hash[js(a[n])]=n;
for (i=n-1;i>=1;i--)
{
t=hash[js(a[i])];
maright[i]=maright[i+1];
if (t!=0)
maright[i]=min(t-1,maright[i]);
hash[js(a[i])]=i;
}
st=1;
ans1=ans2=1;
for (i=2;i<=n;i++)
{
if (a[i]%d!=a[i-1]%d)
{
en=i-1;
does(st,en);
st=i;
}
}
does(st,n);
printf("%d %d",ans1,ans2);
return 0;
}