BZOJ 2989: 数列 二维线段树

2989: 数列

Time Limit: 40 Sec  Memory Limit: 256 MB
Submit: 466  Solved: 211
[Submit][Status][Discuss]

Description

给定一个长度为n的正整数数列a[i]。

定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。

2种操作（k都是正整数）：

1.Modify x k：将第x个数的值修改为k。

2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要 考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计）

Input

第1行两个整数n,q。分别表示数列长度和操作数。

第2行n个正整数，代表初始数列。

第3--q+2行每行一个操作。

Output

对于每次询问操作，输出一个非负整数表示答案

Sample Input

3 5
2 4 3
Query 2 2
Modify 1 3
Query 2 2
Modify 1 2
Query 1 1

Sample Output

2
3
3

HINT

N<=60000 修改操作数<=40000 询问<=50000 Max{a[i]}含修改<=100000

这个题挺显然的

可持久化就是逗你玩儿 实际就是加点

KDT求矩形点数是很明显的做法

为了锻炼数据结构能力写了二维线段树

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
using namespace std;

typedef long long ll;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=10*x+ch-'0';ch=getchar();}
	return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int N=100100,M=20001000;
const int lim[2]={-100000,100000},maxn=160000;

struct seg_tree{int ls,rs,w;}tr[M];
int root[maxn<<2],sz;

void in_modify(int &k,int l,int r,int y)
{
	if(!k) k=++sz;tr[k].w++;
	if(l==r) return ;
	int mid=(l+r)>>1;
	y<=mid ? in_modify(tr[k].ls,l,mid,y) : in_modify(tr[k].rs,mid+1,r,y);
}

void out_modify(int k,int l,int r,int x,int y)
{
	in_modify(root[k],lim[0],lim[1],y);
	if(l==r) return ;int mid=(l+r)>>1;
	x<=mid ? out_modify(k<<1,l,mid,x,y) : out_modify(k<<1|1,mid+1,r,x,y);
}

int in_query(int k,int l,int r,int x,int y)
{
	if(!k) return 0;
	if(l>=x && r<=y) return tr[k].w;
	int mid=(l+r)>>1,s(0),t(0);
	if(x<=mid) s=in_query(tr[k].ls,l,mid,x,y);
	if(y>mid) t=in_query(tr[k].rs,mid+1,r,x,y);
	return s+t;
}

int out_query(int k,int l,int r,int x,int y,int X,int Y)
{
	if(l>=x && r<=y)
	{return in_query(root[k],lim[0],lim[1],X,Y);}
	int mid=(l+r)>>1,s(0),t(0);
	if(x<=mid) s=out_query(k<<1,l,mid,x,y,X,Y);
	if(y>mid) t=out_query(k<<1|1,mid+1,r,x,y,X,Y);
	return s+t;
}

int a[N];

int main()
{
	int n=read(),Q=read();
	register int i,x,K;
	for(i=1;i<=n;++i)
		a[i]=read(),out_modify(1,1,maxn,a[i]+i,a[i]-i);
	char opt[10];
	while(Q--)
	{
		scanf("%s",opt);
		x=read();K=read();
		switch(opt[0])
		{
			case 'Q':
				print(out_query(1,1,maxn,a[x]+x-K,a[x]+x+K,a[x]-x-K,a[x]-x+K));
				puts("");
				break;
			case 'M':
				a[x]=K;
				out_modify(1,1,maxn,K+x,K-x);
				break;
		}
	}
	return 0;
}