WA on #2,3,5,7,8,9,10 40pts

link

#include "bits/stdc++.h"
#define For(i, l, r) for(int i = (l) ; i <= (r) ; ++i)
using namespace std ;
const int N = 1000006 ;
int res[N], p[N], tag[N], length, total ;
int a[N], b[N], n, q ;
inline void init()
{
	length = sqrt(n) ;
	For(i, 1, n)
	{
		p[i] = (i - 1) / length + 1 ;
		res[i] = a[i] ;
	}
}
inline void update(int pos)
{
	int posl = (pos - 1) * length + 1, posr = pos * length ;
	For(i, posl, posr) b[i] = a[i] ;
	sort(b + posl, b + posr + 1) ;
}
inline void add(int l, int r, int w)
{
	int posl = min(p[l] * length, r), posr = max(l, (p[r] - 1) * length + 1) ;
	For(i, l, posl) res[i] += w, a[i] += w ;
	if(p[l] != p[r]) For(i, posr, r) res[i] += w, a[i] += w ;
	For(i, p[l] + 1, p[r] - 1) tag[i] += w ;
	update(p[l]), update(p[r]) ;
}
inline int get(int l, int r, int c)
{
	int posl = min(p[l] * length, r), posr = max(l, (p[r] - 1) * length + 1), ans = 0 ;
	For(i, l, posl) ans += (a[i] + tag[p[i]]) >= c ? 1 : 0 ;
	if(p[l] != p[r]) For(i, posr, r) ans += (a[i] + tag[p[i]]) >= c ? 1 : 0 ;
	For(i, p[l] + 1, p[r] - 1)
	{
		int __l = (i - 1) * length + 1, __r = i * length , mid ;
		while(__l < __r)
		{
			mid = (__l + __r) >> 1 ;
			if(a[mid] + tag[p[mid]] < c) __l = mid + 1 ;
			else __r = mid ;
		}
		ans += i * length - __l + 1 ;
	}
	return ans ;
}
int main()
{
	ios::sync_with_stdio(false) ;
	cin.tie(0) ; cout.tie(0) ;
	cin >> n >> q ;
	For(i, 1, n) cin >> a[i] ;
	init() ;
	For(t, 1, q)
	{
		char op ; int l, r, w, c ;
		cin >> op ;
		if(op == 'M')
		{
			cin >> l >> r >> w ;
			add(l, r, w) ;
		}
		if(op == 'A')
		{
			cin >> l >> r >> c ;
			cout << get(l, r, c) << endl ;
		}
	}
	return 0 ;
}