程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Splay POJ3468(老題新做)

Splay POJ3468(老題新做)

編輯:C++入門知識

Splay POJ3468(老題新做)


A Simple Problem with Integers Time Limit:5000MS Memory Limit:131072KB 64bit IO Format:%I64d & %I64u Submit Status Practice POJ 3468 Appoint description:

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C abc" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q ab" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

Hint

The sums may exceed the range of 32-bit integers.
這題應該算是線段樹區間入目題目,不過還可以用Splay來做,用Splay來維護序列,用到了平衡二叉樹的一個重要的性質那就是中序遍歷是有序的。人生第一道Splay(感人TAT,QAQ)

代碼如下:

/*************************************************************************
    > File Name: Spaly.cpp
    > Author: acvcla
    > QQ: 
    > Mail: [email protected] 
    > Created Time: 2014年11月16日 星期日 00時14分26秒
 ************************************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 100;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
LL add[maxn],sum[maxn];
int ch[maxn][2],siz[maxn],key[maxn],pre[maxn],A[maxn];
int root,tot;
void newnode(int &x,int fa,int Key)//新建節點
{
	x=++tot;
	pre[x]=fa;
	siz[x]=1;
	key[x]=sum[x]=Key;
	ch[x][0]=ch[x][1]=add[x]=0;
}
void Modify(int x,int val){//區間更新
	if(!x)return;
	add[x]+=val;
	key[x]+=val;
	sum[x]+=(LL)val*siz[x];
}
void push_down(int x){//下傳標記
	if(!add[x])return ;
	Modify(ch[x][0],add[x]);
	Modify(ch[x][1],add[x]);
	add[x]=0;
}
void push_up(int x){//更新節點
	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];
}
void built(int &x,int L,int R,int fa){
	if(L>R)return;
	int M=(L+R)>>1;
	newnode(x,fa,A[M]);
	built(ch[x][0],L,M-1,x);
	built(ch[x][1],M+1,R,x);
	push_up(x);
}
void Init(int n)//初始化Spaly,添加了兩個虛擬節點,便於提取區間,避免討論
{
	root=tot=0;
	newnode(root,0,0);
	newnode(ch[root][1],root,0);
	for(int i=1;i<=n;i++)scanf("%d",A+i);
	built(ch[ch[root][1]][0],1,n,ch[root][1]);
	push_up(ch[root][1]);
	push_up(root);
}
void print(int x){
	if(!x)return;
	print(ch[x][0]);
	printf("%d ",key[x]);
	print(ch[x][1]);
}
void Rotate(int x,bool kind){//旋轉,true右旋,false左旋
	int y=pre[x];
	push_down(y);//下傳標記
	push_down(x);

	ch[y][!kind]=ch[x][kind];
	pre[ch[x][kind]]=y;
	ch[x][kind]=y;

	if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;//若y的父節點存在將其孩子指針指向x
	pre[x]=pre[y];
	pre[y]=x;
	push_up(y);//更新回來,需要注意的是,要先更新孩子
	push_up(x);
}
void Spaly(int x,int goal){//伸展操作,將x旋轉到goal下面
	push_down(x);
	while(pre[x]!=goal){
		if(pre[pre[x]]==goal)Rotate(x,ch[pre[x]][0]==x);
		else{
			int y=pre[x];
			bool kind=(ch[pre[y]][0]==y);
			if(ch[y][kind]==x){
				Rotate(x,!kind);
				Rotate(x,kind);
			}else{
				Rotate(y,kind);
				Rotate(x,kind);
			}
		}
	}
	push_up(x);
	if(goal==0)root=x;//如果goal是0說明已經將x旋轉到了根,所以要更新root
}
int Get_kth(int x,int k){//序列中的第k個值
	int t=siz[ch[x][0]]+1;
	if(t==k)return x;
	if(t>k)return Get_kth(ch[x][0],k);
	return Get_kth(ch[x][1],k-t);
}
int main(){
		ios_base::sync_with_stdio(false);
		cin.tie(0);
		siz[0]=sum[0]=0;//不存在的節點初始化為0避免討論
		int n,q,l,r,x;
		scanf("%d%d",&n,&q);
		Init(n);
		char cmd[5];
		while(q--){
			scanf("%s%d%d",cmd,&l,&r);
			Spaly(Get_kth(root,l),0);
			Spaly(Get_kth(root,r+2),root);
			if(cmd[0]=='Q'){
				printf("%lld\n",sum[ch[ch[root][1]][0]]);
			}else{
				int Add;
				scanf("%d",&Add);
				Modify(ch[ch[root][1]][0],Add);
				push_up(ch[root][1]);
				push_up(root);
			}
		}
		return 0;
}



  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved