BCZSX @ 2019-10-22 23:25:35
我太难了，吸臭氧，使用快读还是第八个点TLE……
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXN 1000100
#define MAXM 1010
char opt;
int n, m, num, block, L, R, w, cnt;
int a[MAXN], b[MAXN], gp[MAXN], tag[MAXN], l[MAXM], r[MAXM], belong[MAXN];
inline int read()
{
int res = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res;
}
void pre()
{
block = sqrt(n);
num = n / block;
if (n % block)
++num;
for (int i = 1; i <= num; ++i)
l[i] = (i - 1) * block + 1, r[i] = i * block;
r[num] = n;
}
int main()
{
n = read();
m = read();
pre();
for (int i = 1; i <= n; ++i)
{
a[i] = read();
b[i] = a[i];
belong[i] = (i - 1) / block + 1;
}
for (int i = 1; i <= num; ++i)
sort(b + l[i], b + r[i] + 1);
while (m--)
{
scanf(" %c", &opt);
L = read();
R = read();
w = read();
if (opt == 'M')
{
if (gp[R] - gp[L] <= 1)
{
for (int i = L; i <= R; ++i)
a[i] += w;
for (int i = l[gp[L]]; i <= r[gp[R]]; ++i)
b[i] = a[i];
sort(b + l[gp[L]], b + r[gp[L]] + 1);
if (gp[R] != gp[L])
sort(b + l[gp[R]], b + r[gp[R]] + 1);
}
else
{
for (int i = L; i <= r[gp[L]]; ++i)
a[i] += w;
for (int i = l[gp[R]]; i <= R; ++i)
a[i] += w;
for (int i = gp[L] + 1; i <= gp[R] - 1; ++i)
tag[i] += w;
for (int i = l[gp[L]]; i <= r[gp[L]]; ++i)
b[i] = a[i];
for (int i = l[gp[R]]; i <= r[gp[R]]; ++i)
b[i] = a[i];
sort(b + l[gp[L]], b + r[gp[L]] + 1);
sort(b + l[gp[R]], b + r[gp[R]] + 1);
}
}
else if (opt == 'A')
{
int ans = 0;
if (gp[R] - gp[L] <= 1)
{
for (int i = L; i <= R; ++i)
if (a[i] + tag[gp[i]] >= w)
++ans;
}
else
{
for (int i = L; i <= r[gp[L]]; ++i)
if (a[i] + tag[gp[i]] >= w)
++ans;
for (int i = l[gp[R]]; i <= R; ++i)
if (a[i] + tag[gp[i]] >= w)
++ans;
for (int i = gp[L] + 1; i <= gp[R] - 1; ++i)
{
cnt = lower_bound(b + l[i], b + r[i] + 1, w) - (b + l[i]);
ans += (block - cnt + 1);
}
}
printf("%d\n", ans);
}
}
return 0;
}by Polaris_Dane @ 2019-10-22 23:31:28
@BCZSX 我看看
by BCZSX @ 2019-10-22 23:33:22
别人开O2就过了，我开O3都过不了……
by Polaris_Dane @ 2019-10-22 23:35:33
@BCZSX
我不懂啊。。。
我的程序按理说甚至比你的还要慢一些
但就是能过，还跑的飞快
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<queue>
#define M 1010000
#define inf 0x3f3f3f3f
#define LL long long
using namespace std;
int n,belong[M],m,len,cnt,l[M],r[M],a[M],d[M],p[M];
inline void read(int &x)
{
int f=1;x=0;char s=getchar();
while (!isdigit(s)){
if(s=='-')f=-1;
s=getchar();
}
while (isdigit(s))
{
x=x*10+int(s-'0');
s=getchar();
}
x*=f;
}
void build()
{
cnt=sqrt(n);
len=n/cnt;
if (n%cnt)
{
cnt++;
}
for (int i=1;i<=n;i++)
{
belong[i]=(i-1)/len+1;
d[i]=a[i];
}
for (int i=1;i<=cnt;i++)
{
l[i]=(i-1)*len+1;
r[i]=i*len;
}
r[cnt]=n;
for (int i=1;i<=cnt;i++)
{
sort(d+l[i],d+r[i]+1);
}
}
void change(int le,int re,int v)
{
if (belong[le]==belong[re])
{
for (int i=le;i<=re;i++)
a[i]+=v;
for (int i=l[belong[le]];i<=r[belong[re]];i++)
d[i]=a[i];
sort(d+l[belong[le]],d+r[belong[re]]+1);
}
else
{
for (int i=le;i<=r[belong[le]];i++)
a[i]+=v;
for (int i=l[belong[le]];i<=r[belong[le]];i++)
d[i]=a[i];
sort(d+l[belong[le]],d+r[belong[le]]+1);
for (int i=l[belong[re]];i<=re;i++)
a[i]+=v;
for (int i=l[belong[re]];i<=r[belong[re]];i++)
d[i]=a[i];
sort(d+l[belong[re]],d+r[belong[re]]+1);
for (int i=belong[le]+1;i<=belong[re]-1;i++)
p[i]+=v;
}
}
void ask(int le,int re,int h)
{
int ans=0;
if (belong[le]==belong[re])
{
for (int i=le;i<=re;i++)
{
if (a[i]+p[belong[le]]>=h)
ans++;
}
printf("%d\n",ans);
}
else
{
for (int i=le;i<=r[belong[le]];i++)
{
if (a[i]+p[belong[i]]>=h)
ans++;
}
for (int i=l[belong[re]];i<=re;i++)
{
if (a[i]+p[belong[i]]>=h)
ans++;
}
for (int i=belong[le]+1;i<=belong[re]-1;i++)
{
int pos=lower_bound(d+l[i],d+r[i]+1,h-p[i])-d-l[i];
ans+=(r[i]-l[i]+1-pos);
}
printf("%d\n",ans);
}
}
int main()
{
read(n);read(m);
for (int i=1;i<=n;i++)
{
read(a[i]);
}
build();
while (m--)
{
int t,b,w;
char c;
scanf("\n");
scanf("%c",&c);
if (c=='M')
{
read(t);read(b);read(w);
change(t,b,w);
}
else
{
read(t);read(b);read(w);
ask(t,b,w);
}
}
return 0;
}by Polaris_Dane @ 2019-10-22 23:46:18
@BCZSX 我真心觉得没啥问题。。。
by 1saunoya @ 2019-10-23 12:53:39
// luogu-judger-enable-o2
// Isaunoya
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define int long long
using namespace std ;
#define rep(i , j , n) for(register int i = j ; i <= n ; i ++)
#define Rep(i , j , n) for(register int i = j ; i >= n ; i --)
#define low(x) x & -x
#define go(u) for(register int i = head[u] ; i ; i = e[i].nxt)
inline int read() { register int res = 0 , f = 1 ; register char c = getchar() ;
for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;
for( ; isdigit(c) ; c = getchar()) res = (res << 1) + (res << 3) + (c & 15) ;
return res * f ;
}const static int N = 1000000 + 5 ;
const int Mod = 998244353LL ;
template<typename T> inline void print(T x) { if(x > 9) print(x / 10) ; putchar(x % 10 + '0') ; }
template<typename T> inline void Pr(T x , char c = '\n') { if(x < 0) putchar('-') , x = - x ; print(x) ; putchar(c) ; }
inline int PW(int x , int y , int Mod = Mod) { register int ans = 1 ;
for( ; y ; y >>= 1 , x = (x * x) % Mod) y & 1 ? ans = (ans * x) % Mod : 0 ;
return ans ;
} inline int Inv(int x , int Mod = Mod) { return PW(x , Mod - 2 , Mod) ; }
inline int gc() { register char c = getchar() ;
while(isspace(c)) c = getchar() ;
return c == 'A' ;
}
const int Bl = 1000 + 5;
int n;
int a[N];
struct node {
int add;
std::vector<int> v;
};
node atag[Bl];
int unt;
int bl[N];
inline void reset(int x) {
atag[x].v.clear();
for (register int i = (x - 1) * unt + 1; i <= min(x * unt, n); i++) atag[x].v.push_back(a[i]);
sort(atag[x].v.begin(), atag[x].v.end());
return;
}
inline void change(int l, int r, int c) {
for (register int i = l; i <= min(bl[l] * unt, r); i++) a[i] += c;
reset(bl[l]);
if (bl[l] != bl[r]) {
for (register int i = (bl[r] - 1) * unt + 1; i <= r; i++) a[i] += c;
reset(bl[r]);
}
for (register int i = bl[l] + 1; i <= bl[r] - 1; i++) atag[i].add += c;
}
inline int query(int l, int r, int c) {
int ans = 0;
for (register int i = l; i <= min(bl[l] * unt, r); i++)
if (a[i] + atag[bl[l]].add < c)
ans++;
if (bl[l] != bl[r]) {
for (register int i = (bl[r] - 1) * unt + 1; i <= r; i++)
if (a[i] + atag[bl[r]].add < c)
ans++;
}
for (register int i = bl[l] + 1; i <= bl[r] - 1; i++) {
int s = c - atag[i].add;
ans += lower_bound(atag[i].v.begin(), atag[i].v.end(), s) - atag[i].v.begin();
}
return ans;
}
signed main() {
n = read(); int t = read() ; unt = sqrt(n) ;
for (register int i = 1; i <= n; i++) a[i] = read();
for (register int i = 1; i <= n; i++) bl[i] = (i - 1) / unt + 1;
for (register int i = 1; i <= n; i++) {
atag[bl[i]].v.push_back(a[i]);
}
for (register int i = 1; i <= bl[n]; i++) {
sort(atag[i].v.begin(), atag[i].v.end());
}
for( ; t -- ; ) {
int opt = gc() ;
int l = read() , r = read() , c = read() ;
if(opt == 0) {
change(l , r , c) ;
}
if(opt == 1) {
Pr((r - l + 1) - query(l , r , c)) ;
// rep(i , 1 , n) Pr(a[i] + atag[bl[i]].add , ' ') ;
// puts("") ;
}
}
return 0;
}