Thαm @ 2020-01-15 20:08:33
40分，不知道为什么错了，样例是过了的
#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define in(n) n = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define Min(a,b) a < b ? a : b
#define Max(a,b) a > b ? a : b
#define ll long long
#define New ll
#define rg register
using namespace std;
namespace IO_Optimization
{
inline New read()
{
New X = 0,w = 0;
char ch = 0;
while(!isdigit(ch))
{
w |= ch == '-';
ch=getchar();
}
while(isdigit(ch))
{
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
inline void write(long long x)
{
if(x < 0) putchar('-'),x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO_Optimization;
const int MAXN = 1000000 + 2;
int n,q,m,x,y,z;
int a[MAXN],pos[MAXN],lazy[MAXN];
vector<int>v[MAXN];
inline void upd(int x)
{
v[x].clear();
int tmp = Min(x * m,n);
for(rg int i = (x - 1) * m + 1;i <= tmp; ++i)
v[x].push_back(a[i]);
sort(v[x].begin(),v[x].end());
}
inline void add(int l,int r,int k)
{
int tmp = Min(pos[l] * m,r);
for(rg int i = l;i <= tmp;++i)a[i] += k;
tmp = pos[l] * m;
upd(pos[l]);
if(pos[l] != pos[r])
{
for(rg int i = (pos[r] - 1) * m + 1;i <= r; ++i)
a[i] += k;
upd(pos[r]);
}
for(rg int i = pos[l] + 1;i < pos[r]; ++i)lazy[i] += k;
}
inline int work(int l,int r,int k)
{
int ans = 0;
int tmp = Min(pos[l] * m,r);
for(rg int i = l;i <= tmp;++i)
if(a[i] + lazy[pos[i]] < k)
++ans;
if(pos[l] != pos[r])
for(rg int i = (pos[r] - 1) * m + 1;i <= r; ++i)
if(a[i] + lazy[pos[i]] < k)
++ans;
for(rg int i = pos[l] + 1;i < pos[r]; ++i)
{
int t = k - lazy[i];
ans += lower_bound(v[i].begin(),v[i].end(),t) - v[i].begin();
}
return r - l + 1 - ans;
}
int main()
{
in(n);m = sqrt(n);
in(q);
for(rg int i = 1;i <= n; ++i)
in(a[i]),pos[i] = (i - 1) / m + 1,v[pos[i]].push_back(a[i]);
for(rg int i = 1;i <= q; ++i)
{
char c;cin>>c;
in(x),in(y),in(z);
if(c == 'M')add(x,y,z);
if(c == 'A')
outn(work(x,y,z));
}
return 0;
}by 君のNOIP。 @ 2020-03-02 20:03:10
花里胡哨
by 君のNOIP。 @ 2020-03-02 20:03:28
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define G() Cr=getchar()
int Xr;char Cr;
inline int rd(){
Xr=0,G();
while(Cr>'9'||Cr<'0')G();
while(Cr>='0'&&Cr<='9')Xr=(Xr<<3)+(Xr<<1)+Cr-'0',G();
return Xr;
}
#define MAX_N 1000002
#define MAX_M 10000
int n,q;
int va[MAX_N],pos[MAX_N],vb[MAX_N];
int block,ans,num;
int add[MAX_M],l[MAX_M],r[MAX_M];
char c;
int L,R,X;
int find(int t,int x){
int ll=l[t],rr=r[t];
int s=r[t]+1;
while(ll<=rr){
int mid=(ll+rr)>>1;
if(vb[mid]+add[t]>=x)s=mid,rr=mid-1;
else ll=mid+1;
}
return r[t]-s+1;
}
int main(){
n=rd(),q=rd();
block=(int)sqrt(n);
num=(n-1)/block+1;
for(int i=1;i<=n;i++)va[i]=rd(),vb[i]=va[i],pos[i]=(i-1)/block+1;
for(int i=1;i<=num;i++){
l[i]=(i-1)*block+1,r[i]=i*block;
sort(vb+l[i],vb+r[i]+1);
}
r[num]=n;
while(q--){
c=getchar();
while(c!='A'&&c!='M')c=getchar();
L=rd(),R=rd(),X=rd();
if(c=='M'){
if(pos[L]==pos[R]){
for(int i=L;i<=R;i++)va[i]+=X;
for(int i=l[pos[L]];i<=r[pos[L]];i++)vb[i]=va[i];
sort(vb+l[pos[L]],vb+r[pos[L]]+1);
}
else{
for(int i=L;i<=r[pos[L]];i++)va[i]+=X;
for(int i=l[pos[L]];i<=r[pos[L]];i++)vb[i]=va[i];
sort(vb+l[pos[L]],vb+r[pos[L]]+1);
for(int i=pos[L]+1;i<pos[R];i++)add[i]+=X;
for(int i=l[pos[R]];i<=R;i++)va[i]+=X;
for(int i=l[pos[R]];i<=r[pos[R]];i++)vb[i]=va[i];
sort(vb+l[pos[L]],vb+r[pos[L]]+1);
}
}
else{
ans=0;
if(pos[L]==pos[R]){
for(int i=L;i<=R;i++)ans+=(va[i]+add[pos[L]]>=X);
}
else{
for(int i=L;i<=r[pos[L]];i++)ans+=(va[i]+add[pos[L]]>=X);
for(int i=pos[L]+1;i<pos[R];i++)ans+=find(i,X);
for(int i=l[pos[R]];i<=R;i++)ans+=(va[i]+add[pos[L]]>=X);
}
printf("%d\n",ans);
}
}
}