POJ3468splay

作者：招聘HR | 来源：互联网 | 2023-09-25 15:34

ASimpleProblemwithIntegersTimeLimit:5000MS MemoryLimit:131072KTotalSub

A Simple Problem with Integers

Time Limit: 5000MS		Memory Limit: 131072K
Total Submissions: 54382		Accepted: 16350
Case Time Limit: 2000MS

Description

You have N integers, A₁, A₂, ... ,
A_N. 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 A₁,
A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a,
A_a_&＃43;1, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a_&＃43;1, ... ,
A_b.

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。
代码：

/* ***********************************************
Author :rabbit
Created Time :2014/3/22 15:21:19
File Name :13.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
#define keytree ch[ch[root][1]][0]
const ll maxn=200100;
struct splay{
ll sz[maxn],ch[maxn][2],pre[maxn];
ll root,top1,top2;
ll ss[maxn],que[maxn];
void Rotate(ll x,ll f){
ll y=pre[x];
pushdown(y);
pushdown(x);
ch[y][!f]=ch[x][f];
pre[ch[x][f]]=y;
pre[x]=pre[y];
if(pre[x])ch[pre[y]][ch[pre[y]][1]==y]=x;
ch[x][f]=y;
pre[y]=x;
pushup(y);
}
void Splay(ll x,ll goal){
pushdown(x);
while(pre[x]!=goal){
if(pre[pre[x]]==goal)Rotate(x,ch[pre[x]][0]==x);
else{
ll y=pre[x],z=pre[y];
ll f=ch[z][0]==y;
if(ch[y][f]==x)Rotate(x,!f),Rotate(x,f);
else Rotate(y,f),Rotate(x,f);
}
}
pushup(x);
if(goal==0)root=x;
}
void RTO(ll k,ll goal){
ll x=root;
pushdown(x);
while(sz[ch[x][0]]!=k){
if(k else{
k-=sz[ch[x][0]]+1;
x=ch[x][1];
}
pushdown(x);
}
Splay(x,goal);
}
void erase(ll x){
ll father=pre[x];
ll head=0,tail=0;
for(que[tail++]=x;head ss[top2++]=que[head];
if(ch[que[head]][0])que[tail++]=ch[que[head]][0];
if(ch[que[head]][1])que[tail++]=ch[que[head]][1];
}
ch[father][ch[father][1]==x]=0;
pushup(father);
}
void debug(){
printf("%lld\n",root);
Traval(root);
}
void Traval(ll x){
if(x){
Traval(ch[x][0]);
printf("结点%2lld:左儿子 %2lld 右儿子 %2lld 父结点 %2lld size = %2lld ,val = %2lld\n",x,ch[x][0],ch[x][1],pre[x],sz[x],val[x]);
Traval(ch[x][1]);
}
}
ll val[maxn],num[maxn],add[maxn],sum[maxn];
void Newnode(ll &x,ll c){
if(top2)x=ss[--top2];else x=++top1;
ch[x][0]=ch[x][1]=pre[x]=0;
sz[x]=1;
val[x]=sum[x]=c;
add[x]=0;
}
void pushdown(ll x){
if(add[x]){
val[x]+=add[x];
add[ch[x][0]]+=add[x];
add[ch[x][1]]+=add[x];
sum[ch[x][0]]+=sz[ch[x][0]]*add[x];
sum[ch[x][1]]+=sz[ch[x][1]]*add[x];
add[x]=0;
}
}
void pushup(ll x){
sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]];
sum[x]=add[x]+val[x]+sum[ch[x][0]]+sum[ch[x][1]];
}
void Build(ll &x,ll l,ll r,ll f){
if(l>r)return;
ll m=(l+r)/2;
Newnode(x,num[m]);
Build(ch[x][0],l,m-1,x);
Build(ch[x][1],m+1,r,x);
pre[x]=f;
pushup(x);
}
void init(ll n){
ch[0][0]=ch[0][1]=pre[0]=sz[0]=0;
add[0]=sum[0]=0;
Newnode(root,-1);
Newnode(ch[root][1],-1);
pre[top1]=root;
sz[root]=2;
for(ll i=0;i Build(keytree,0,n-1,ch[root][1]);
pushup(ch[root][1]);
pushup(root);
}
void update(ll l,ll r,ll c){
RTO(l-1,0);
RTO(r+1,root);
add[keytree]+=c;
sum[keytree]+=c*sz[keytree];
}
ll query(ll l,ll r){
RTO(l-1,0);
RTO(r+1,root);
return sum[keytree];
}
}spt;
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ll n,m;
while(~scanf("%lld%lld",&n,&m)){
spt.init(n);
while(m--){
char op[2];
scanf("%s",op);
if(op[0]==‘Q‘){
ll l,r,c;
scanf("%lld%lld",&l,&r);
printf("%lld\n",spt.query(l,r));
}
else{
ll l,r,c;
scanf("%lld%lld%lld",&l,&r,&c);
spt.update(l,r,c);
}
}
}
return 0;
}

POJ 3468 splay,布布扣,bubuko.com

推荐阅读

schema
MySQL显示SQL语句执行时间的实例详解

本文详细介绍了如何使用MySQL来显示SQL语句的执行时间，并通过MySQL Query Profiler获取CPU和内存使用量以及系统锁和表锁的时间。同时介绍了效能分析的三种方法：瓶颈分析、工作负载分析和基于比率的分析。 ... [详细]

蜡笔小新 2023-12-12 16:16:42
main
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
main
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
main
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
main
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
main
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
php
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
command
VB.NET在线急等问题解决方法，如何统计数据库字段下的数据并显示在文本框里？

本文介绍了一个在线急等问题解决方法，即如何统计数据库中某个字段下的所有数据，并将结果显示在文本框里。作者提到了自己是一个菜鸟，希望能够得到帮助。作者使用的是ACCESS数据库，并且给出了一个例子，希望得到的结果是560。作者还提到自己已经尝试了使用"select sum(字段2) from 表名"的语句，得到的结果是650，但不知道如何得到560。希望能够得到解决方案。 ... [详细]

蜡笔小新 2023-12-13 15:15:30
input
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
php
高质量SQL书写的30条建议

本文提供了30条关于优化SQL的建议，包括避免使用select *，使用具体字段，以及使用limit 1等。这些建议是基于实际开发经验总结出来的，旨在帮助读者优化SQL查询。 ... [详细]

蜡笔小新 2023-12-13 13:24:33
php
Html5-Canvas实现简易的抽奖转盘效果

本文介绍了如何使用Html5和Canvas标签来实现简易的抽奖转盘效果，同时使用了jQueryRotate.js旋转插件。文章中给出了主要的html和css代码，并展示了实现的基本效果。 ... [详细]

蜡笔小新 2023-12-13 06:02:20
main
3.223.28周学习总结中的贪心作业收获及困惑

本文是对3.223.28周学习总结中的贪心作业进行总结，作者在解题过程中参考了他人的代码，但前提是要先理解题目并有解题思路。作者分享了自己在贪心作业中的收获，同时提到了一道让他困惑的题目，即input details部分引发的疑惑。 ... [详细]

蜡笔小新 2023-12-13 03:42:02
php
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
php
VScode格式化文档换行或不换行的设置方法

本文介绍了在VScode中设置格式化文档换行或不换行的方法，包括使用插件和修改settings.json文件的内容。详细步骤为：找到settings.json文件，将其中的代码替换为指定的代码。 ... [详细]

蜡笔小新 2023-12-14 17:15:38
web
javascript – 概述在Firefox上无法正常工作

我试图提出一些自定义大纲,以达到一些Web可访问性建议.但我不能用Firefox制作.这就是它在Chrome上的外观：而那个图标实际上是一个锚点.在Firefox上,它只概述了整个 ... [详细]

蜡笔小新 2023-12-14 10:20:38

招聘HR

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章