Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
45128 Ryan123 数列操作1 C++ 通过 100 325 MS 2048 KB 1541 2022-02-15 13:50:08

Tests(10/10):


#include <bits/stdc++.h> using namespace std; vector<int> vec[50001]; int lazy[50001],bl[50001],a[50001],block,n; int Reset(int now) { vec[now].clear(); for(int i=(now-1)*block+1; i<=min(n,block*now); i++) vec[now].push_back(a[i]); sort(vec[now].begin(),vec[now].end()); } int Search(int l,int r,int x) { int cnt=0; for(int i=l; i<=min(r,bl[l]*block); i++) if(a[i]+lazy[bl[i]]<x) cnt++; if(bl[l]^bl[r]) for(int i=max((bl[r]-1)*block+1, l); i<=r; i++) if(a[i]+lazy[bl[i]]<x) cnt++; for(int i=bl[l]+1; i<=bl[r]-1; i++) cnt+=lower_bound(vec[i].begin(),vec[i].end(),x-lazy[i])-vec[i].begin(); return cnt; } int Add(int l,int r,int x) { for(int i=l; i<=min(r,bl[l]*block); i++) a[i]+=x; Reset(bl[l]); if(bl[l]!=bl[r]) { for(int i=block*(bl[r]-1)+1; i<=r; i++) a[i]+=x; Reset(bl[r]); } for(int i=bl[l]+1; i<=bl[r]-1; i++) lazy[i]+=x; } inline int Read() { int x=0,f=0; char c=getchar(); for(; c<'0' || c>'9'; f^=(c=='-'),c=getchar()); for(; c<='9' && c>='0'; c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return f?-x:x; } int main() { n=Read(); block=sqrt(n); for(int i=1; i<=n; i++) a[i]=Read(); for(int i=1; i<=n; i++) { bl[i]=(i-1)/block+1; vec[bl[i]].push_back(a[i]); } for(int i=1;i<=bl[n];i++) sort(vec[i].begin(),vec[i].end()); for(int i=1; i<=n; i++) { int opt=Read(),l=Read(),r=Read(),x=Read(); if(opt==0) Add(l,r,x); if(opt==1) cout<<Search(l,r,x*x)<<'\n'; } return 0; }


测评信息: