P2801
题意：一个序列，两种操作
- 1 区间加上一个数
- 2 给定 \(x\) 区间查询有多少个数大于 \(x\)
暴力分块搞
很难搞多少个数大于
考虑维护每个小块的排序好的数组 每次修改小块完排序 大块打标记
查询时二分一下即可
时间复杂度 \(O(q\sqrt n \log n)\)
#include<bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
int n,m;
ll mod;
int block,tot,L[1005],R[1005],bel[N];
int tag[1005],a[N],d[N];
void reset(int x)
{
for(int i=L[x];i<=R[x];i++)
d[i]=a[i];
sort(d+L[x],d+1+R[x]);
}
void build()
{
block=sqrt(n);
tot=n/block;
if(n%block) tot++;
for(int i=1;i<=tot;i++)
L[i]=R[i-1]+1,R[i]=i*block,reset(i);
R[tot]=n;
for(int i=1;i<=n;i++)
bel[i]=(i-1)/block+1;
}
void updata(int l,int r,int k)
{
int ls=bel[l],rs=bel[r];
if(ls==rs)
{
for(int i=l;i<=r;i++)
a[i]+=k;
reset(ls);
return;
}
for(int i=l;i<=R[ls];i++)
a[i]+=k;
reset(ls);
for(int i=L[rs];i<=r;i++)
a[i]+=k;
reset(rs);
for(int i=ls+1;i<=rs-1;i++)
tag[i]+=k;
}
int query(int l,int r,int k)
{
int ls=bel[l],rs=bel[r],ans=0;
if(ls==rs)
{
for(int i=l;i<=r;i++)
if(a[i]+tag[ls]>=k) ans++;
return ans;
}
for(int i=l;i<=R[ls];i++)
if(tag[ls]+a[i]>=k) ans++;
for(int i=L[rs];i<=r;i++)
if(tag[rs]+a[i]>=k) ans++;
for(int i=ls+1;i<=rs-1;i++)
ans+=R[i]-(lower_bound(d+L[i],d+1+R[i],k-tag[i])-d)+1;
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
build();
while(m--)
{
char c;
int l,r,x;
cin>>c>>l>>r>>x;
if(c=='M')
updata(l,r,x);
else
cout<<query(l,r,x)<<"\n";
}
return 0;
}
P4145
题意：给定序列，两种操作
- 查询一段区间和
- 对一段区间每个数 \(x\to \sqrt x\)
根据每个数最多只会开根 \(12\) 次打标记看看哪些区间不用修改跳过即可
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
int n,m;
int block,tot,L[N],R[N],bel[N];
ll a[N],sum[N],tag[N];
void build()
{
block=sqrt(n);
tot=n/block;
if(n%block) tot++;
for(int i=1;i<=n;i++)
bel[i]=(i-1)/block+1,sum[bel[i]]+=a[i];
for(int i=1;i<=tot;i++)
L[i]=R[i-1]+1,R[i]=i*block;
R[tot]=n;
}
void modify(int l,int r)
{
int ls=bel[l],rs=bel[r];
if(ls==rs)
{
for(int i=l;i<=r;i++)
sum[ls]-=a[i],a[i]=sqrt(a[i]),sum[ls]+=a[i];
return;
}
for(int i=l;i<=R[ls];i++)
{
sum[ls]-=a[i];
a[i]=sqrt(a[i]);
sum[ls]+=a[i];
}
for(int i=L[rs];i<=r;i++)
{
sum[rs]-=a[i];
a[i]=sqrt(a[i]);
sum[rs]+=a[i];
}
for(int i=ls+1;i<=rs-1;i++)
if(sum[i]>R[i]-L[i]+1)
{
sum[i]=0;
for(int j=L[i];j<=R[i];j++)
a[j]=sqrt(a[j]),sum[i]+=a[j];
}
}
ll query(int l,int r)
{
ll ans=0;
int ls=bel[l],rs=bel[r];
if(ls==rs)
{
for(int i=l;i<=r;i++)
ans+=a[i];
return ans;
}
for(int i=l;i<=R[ls];i++)
ans+=a[i];
for(int i=L[rs];i<=r;i++)
ans+=a[i];
for(int i=ls+1;i<=rs-1;i++)
ans+=sum[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
build();
scanf("%d",&m);
while(m--)
{
int opr,l,r;
scanf("%d%d%d",&opr,&l,&r);
if(l>r) swap(l,r);
if(opr) printf("%lld\n",query(l,r));
else modify(l,r);
}
return 0;
}
P4168
十分重要的一道题
给定一个序列 每次问一段区间的众数
这道题有一个思想：预处理
因为是静态区间 可以用 \(O(n\sqrt n)\) 的时间预处理好每一块到另一块的众数
这样只需要枚举一下小块的数和一个大众数即可
时间复杂度 \(O(n\sqrt n)\)
#include<bits/stdc++.h>
#define N 40005
#define ll long long
using namespace std;
int n,m,sum[N];
int block,tot,L[1205],R[1205],bel[N];
int a[N],b[N];
int s[1205][N],f[1205][1205];
// s 前缀和 f i,j i->j块众数
void build()
{
block=pow(n,(1.0/3));
tot=n/block;
if(n%block) tot++;
for(int i=1;i<=tot;i++)
L[i]=R[i-1]+1,R[i]=i*block;
R[tot]=n;
for(int i=1;i<=n;i++)
bel[i]=(i-1)/block+1;
for(int i=1;i<=n;i++)
for(int j=bel[i];j<=tot;j++)
s[j][a[i]]++;
for(int i=1;i<=tot;i++)
{
for(int j=i;j<=tot;j++)
{
f[i][j]=f[i][j-1];
for(int k=L[j];k<=R[j];k++)
{
sum[a[k]]++;
if(sum[a[k]]>sum[f[i][j]]||sum[a[k]]==sum[f[i][j]]&&a[k]<f[i][j]) f[i][j]=a[k];
}
}
for(int j=L[i];j<=n;j++)
sum[a[j]]=0;
}
}
int query(int l,int r)
{
int ls=bel[l],rs=bel[r],ans=0;
if(rs-ls<=2)
{
for(int i=l;i<=r;i++)
{
sum[a[i]]++;
if(sum[a[i]]>sum[ans]||sum[a[i]]==sum[ans]&&ans>a[i]) ans=a[i];
}
for(int i=l;i<=r;i++)
sum[a[i]]=0;
return ans;
}
for(int i=l;i<=R[ls];i++) sum[a[i]]=s[rs-1][a[i]]-s[ls][a[i]];
for(int i=L[rs];i<=r;i++) sum[a[i]]=s[rs-1][a[i]]-s[ls][a[i]];
for(int i=l;i<=R[ls];i++)
{
sum[a[i]]++;
if(sum[a[i]]>sum[ans]||sum[a[i]]==sum[ans]&&ans>a[i]) ans=a[i];
}
for(int i=L[rs];i<=r;i++)
{
sum[a[i]]++;
if(sum[a[i]]>sum[ans]||sum[a[i]]==sum[ans]&&ans>a[i]) ans=a[i];
}
int t=f[ls+1][rs-1],v=s[rs-1][t]-s[ls][t];
for(int i=l;i<=R[ls];i++) v+=(a[i]==t);
for(int i=L[rs];i<=r;i++) v+=(a[i]==t);
if(v>sum[ans]||v==sum[ans]&&ans>t) ans=t;
for(int i=l;i<=R[ls];i++) sum[a[i]]=0;
for(int i=L[rs];i<=r;i++) sum[a[i]]=0;
return ans;
}
int main()
{
// freopen("P4168_1.in","r",stdin);
// freopen("my.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int len=unique(b+1,b+1+n)-b;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+len,a[i])-b;
build();
int last=0;
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
l=(l+last-1)%n+1;
r=(r+last-1)%n+1;
if(l>r) swap(l,r);
last=b[query(l,r)];
printf("%d\n",last);
}
return 0;
}