P2801 教主的魔法

rt，给出代码，注意 $klen$ 表示块长，提交记录。

AC CODE

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

int n , q , klen , a[1000050] , t[1000050] , bel[1000050];
char op;

struct Kuai {
	int st , ed , ad;
}f[2050];

int Getnum (int x)
{
	if(x % klen == 0) return x / klen;
	return x / klen + 1;
}

void Sort_T (int x)
{
	for(int i = f[x].st ; i <= f[x].ed ; i ++) 
	{
		t[i] = a[i];
	}
	sort (t+f[x].st , t+1+f[x].ed);
	return;
}

void Update (int l , int r , int k)
{
	int ax = bel[l] , by = bel[r];
	if(ax == by)
	{
		for(int i = l ; i <= r ; i ++)
		{
			a[i] += k;
		}
		Sort_T(ax);
		return;
	}
	
	for(int i = l ; i <= f[ax].ed ; i ++)
	{
		a[i] += k;
	}
	for(int i = f[by].st ; i <= r ; i ++)
	{
		a[i] += k;
	}
	Sort_T(ax);
	Sort_T(by);
	for(int i = ax+1 ; i <= by-1 ; i ++)
	{
		f[i].ad += k;
	}
	return;
}

int binary (int l , int r , int key)
{
	int mid;
	while (l < r)
	{
		mid = (l+r)>>1;
		if(t[mid] >= key) r = mid;
		else l = mid + 1;
	}
	return l;
}

int Solve (int l , int r , int k)
{
	int ax = bel[l] , by = bel[r] , ans = 0;
	if(ax == by)
	{
		for(int i = l ; i <= r ; i ++)
		{
			if(a[i] >= k - f[ax].ad) ++ ans;
		}
		return ans;
	}
	
	for(int i = l ; i <= f[ax].ed ; i ++)
	{
		if(a[i] >= k - f[ax].ad) ++ ans;
	}
	
	for(int i = f[by].st ; i <= r ; i ++)
	{
		if(a[i] >= k - f[ax].ad) ++ ans;
	}
	
	for(int i = ax+1 ; i <= by-1 ; i ++)
	{
		int z = binary(f[i].st , f[i].ed , k - f[i].ad);
		if(t[z] >= k - f[i].ad)
		{
			ans += f[i].ed - z + 1;
		}
	}
	return ans;
}

int main()
{
	scanf("%d%d",&n,&q);
	klen = sqrt(n)-1;
  // 注意这个块长
	for(int i = 1 ; i <= n ; i ++)
	{
		scanf("%d",&a[i]);
		bel[i] = Getnum(i);
	}
	
	for(int i = 1 ; i <= n ; i ++)
	{
		f[bel[i]].ad = 0;
		if(bel[i] != bel[i-1])
		{
			f[bel[i]].st = i;
		}
		if(bel[i] != bel[i+1]) 
		{
			f[bel[i]].ed = i;
			Sort_T(bel[i]);
		}
//		printf("i = %d  num = %d  st = %d  ed = %d\n",i,bel[i],f[bel[i]].st,f[bel[i]].ed);
	}
	
	while (q --)
	{
		cin >> op;
		int l , r , z;
		scanf("%d%d%d",&l,&r,&z);
		if(op == 'M')
		{
			Update (l , r , z);
		}
		if(op == 'A')
		{
			printf("%d\n",Solve(l , r , z));
		}
	}
	
	return 0;
}

当 $klen = \sqrt{n}-1$ 时可以通过此题；

当 $klen = \sqrt{n}$ 时可以通过原数据，无法通过 HACK1。

当 $klen = \sqrt{n}+1$ 时可以通过 HACK 数据，无法通过原数据点12。

由此想问一下分块的块长是否对答案有影响。

HACK1:

Input:

100 5
40 7 47 44 52 81 87 60 82 49 40 30 44 90 62 68 81 44 46 17 44 71 89 79 44 95 57 4 6 36 26 61 62 64 14 93 46 35 20 98 55 6 71 9 85 31 1 70 93 100 82 33 57 14 83 56 40 67 27 53 43 39 44 4 59 32 49 72 91 60 67 84 16 64 9 21 59 30 100 34 47 62 10 9 56 88 19 20 16 92 22 11 68 56 62 16 77 94 20 10
M 66 67 1
M 82 97 13
M 14 90 20
M 47 76 7
A 58 86 80

Output

13