今天码力不足还有点丧，不应该这样哦，学习新东西应该是一件很开心的事情。
昨天学的一种优美的暴力方法，分块。
找了个题试试这个方法，结果优化失败T掉了，主要就是最后没有想到逆序求f数组与to数组，
因为前面的值可以通过后面的值推出的，简单加一就好。
一开始只能想到直接顺序暴力求f还有更新，被卡掉了。
日常感叹我好菜呀
Bounce 弹飞绵羊
VJ题目链接：https://vjudge.net/problem/HYSBZ-2002
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=2e5+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,m,block;
int k[MAXN];
int pos[MAXN];//
int f[MAXN];//从一个点出发跳出所在块所需要的步数
int to[MAXN];//从一个点出发跳出块后到达哪
int query(int x)
{
int ans=0;
for(int i=x;i<=n;i=to[i])
ans+=f[i];
return ans;
}
void update(int x,int v)
{
k[x]=v;
for(int i=x;i>=(pos[x]-1)*block+1;i--)
{
if(i+k[i]>pos[i]*block||i+k[i]>n)
{
f[i]=1;
to[i]=i+k[i];
}
else
{
f[i]=f[i+k[i]]+1;
to[i]=to[i+k[i]];
}
}
}
int main()
{
while(~s1(n))
{
// init
for(int i=1;i<=n;i++) s1(k[i]);
block=sqrt(n);
for(int i=1;i<=n;i++)
pos[i]=(i-1)/block+1;
for(int i=n;i>=1;i--)//怎么就想不到前面的步数可以用后面的步数+1，T哭
{
if(i+k[i]>pos[i]*block||i+k[i]>n)
{
f[i]=1;
to[i]=i+k[i];
}
else
{
f[i]=f[i+k[i]]+1;
to[i]=to[i+k[i]];
}
}
// for(int i=1;i<=n;i++)
// printf("pos[%d]=%d f[%d]=%d to[%d]=%d\n",i,pos[i],i,f[i],i,to[i]);
int m;s1(m);
while(m--)
{
int i,j,v;
s1(i);
if(i==1)
{
s1(j);
j++;
printf("%d\n",query(j));
}
else
{
s2(j,v);
j++;
update(j,v);
}
}
}
return 0;
}
P2801 教主的魔法
洛谷题目链接：https://www.luogu.org/problem/P2801
大概是个分块水题，主要涉及的就是区间修改和区间查询
暴力分块加二分查找，然而T掉了，找了找博客感觉思路没差，，，
学过分块之后做了两个题都T掉了，，，我没掌握到精髓。
明天再改一下代码吧。
/19/8/2
改了一小时，，，终于给过了
原来T掉是因为自己代码写的太丑，，，很多边界闭着眼码都码错了。
边界改好后又开始蛙，因为二分没写对。
写码还是仔细点八。
/19/8/3
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000009
#define endll printf("\n")
#define s1(a) scanf("%d",&a)
#define s2(a,b) scanf("%d %d",&a,&b)
#define mem(a,b) memset(a,b,sizeof(a))
#define s3(a,b,c) scanf("%d %d %d",&a,&b,&c)
int n,m,q,block;//m块数
int h[MAXN];//原数组
int f[MAXN];//分块排序之后的数组
int pos[MAXN];
int lazy[MAXN];//某块中的操作值
void reset(int x)//更新某块
{
int l=(x-1)*block+1,r=min(x*block,n);
for(int i=l;i<=r;i++)
f[i]=h[i];
sort(f+l,f+r+1);
}
void update(int l,int r,int w)
{
if(pos[l]==pos[r])
{
for(int i=l;i<=r;i++) h[i]+=w;
}
else
{
for(int i=l;i<=pos[l]*block;i++) h[i]+=w;
for(int i=(pos[r]-1)*block+1;i<=r;i++) h[i]+=w;
}
reset(pos[l]);
reset(pos[r]);
for(int i=pos[l]+1;i<pos[r];i++)
lazy[i]+=w;
}
int query(int l,int r,int w)
{
int ans=0;
if(pos[l]==pos[r])
{
for(int i=l;i<=r;i++)
if(h[i]+lazy[pos[i]]>=w)
ans++;
}
else
{
for(int i=l;i<=pos[l]*block;i++)
if(h[i]+lazy[pos[i]]>=w)
ans++;
for(int i=(pos[r]-1)*block+1;i<=r;i++)
if(h[i]+lazy[pos[i]]>=w)
ans++;
}
for(int k=pos[l]+1;k<pos[r];k++)
{
int l=(k-1)*block+1,r=min(k*block,n);
r++;//左开右闭右边界记得处理啊。。
while(l<r)
{
int mid=(l+r)>>1;
if(f[mid]+lazy[k]>=w)
r=mid;
else
l=mid+1;
}
ans+=min(k*block,n)-l+1;
}
//闭区间写法
// for(int k=pos[l]+1;k<pos[r];k++)
// {
// int l=(k-1)*block+1,r=min(k*block,n);
// while(l<=r)
// {
// int mid=(l+r)>>1;
// if(f[mid]+lazy[k]>=w)
// r=mid-1;
// else
// l=mid+1;
// }
// ans+=min(k*block,n)-l+1;
// }
return ans;
}
int main()
{
s2(n,q);
block=sqrt(n);
for(int i=1;i<=n;i++)
{
s1(h[i]);
pos[i]=(i-1)/block+1;
}
m=n/block+(n%block!=0);
for(int i=1;i<=m;i++)
reset(i);
while(q--)
{
char s[5];
int l,r,w;
scanf("%s",s);
s3(l,r,w);
if(s[0]=='M')
update(l,r,w);
else
printf("%d\n",query(l,r,w));
}
return 0;
}
京公网安备 11010502036488号