估分:60+40+100=200
实际:60+40+30=130
Rank 9
萎的一批
好歹把T1T2的暴力分拿满了
比赛的时候想了很久没有思路，就打暴力把人一个个塞进去，拿了暴力分60分
操作一：
首先，放人进去的时候，优先级是固定的。所以我们可以用后序遍历把优先级搞出来，用一个堆来维护哪些位置是空的，每次放人的时候就从堆里面找一个位置，删人的时候放一个位置进堆里面。(用线段树也可以搞，我就是用线段树打的)
操作二：
我们已经知道哪些点有人，那么把一个人删去时，就用倍增找到他最上面一个有人的节点，把它删去就好了。(用树链剖分也可以搞，cgh打了树剖)
比赛的时候想了很久也没什么思路，就把40分暴力分给拿到了。
首先考虑一种暴力：设f[i][0/1]表示前面的数与i进行位运算，结果的最大值和方案数。这样子做插入是O(\(2^{16}\))的,询问是O(1)的。
怎么平衡一下插入和询问的时间复杂度呢？
运用广义平衡规划的思想，类似折半搜索一样，设f[i][j][0/1]表示前面的数中，前八位为i,与某个后八位为j的数进行位运算，后八位结果的最大值和方案数。
这样一来，插入时i是固定的，我们只用枚举j来更新f；而询问时j是固定的，只用枚举i来更新ans。
~好巧妙的思想啊~
谴责出题人，暴力随便水过。
我以为它是满足二分性的，结果又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}\}+1\leq r-l+1+k\)即可更新答案。
考虑枚举左端点，找最大的右端点
设ma[r]表示当左端点为l时的\(max\{a_{l...r}\}\),mi[r]表示当左端点为l时的\(min\{a_{l...r}\}\)
化一下式子变成\(ma[r]-mi[r]-r\leq 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; }转载于:https://www.cnblogs.com/leason-lyx/p/11148099.html
