#include <iostream>
#include <fstream>
using namespace std;
ifstream fin( "in.in" );
ofstream fout( "out.out" );
struct info
{
long long l;
long long r;
long long sum;
};
info a[400000];
long long n , q;
long long s[400000];
long long A , B , C;
char ch[2];
void
set( long long l , long long r , long long cur )
{
a[cur].l = l;
a[cur].r = r;
a[cur].sum = 0;
if( l == r ) return ;
set( l , ( l + r ) / 2 , cur * 2 );
set( ( l + r ) / 2 + 1 , r , cur * 2 + 1 );
}
void
insert( long long l , long long r , long long cur , long long delta )
{
long long mid = ( a[cur].l + a[cur].r ) / 2;
long long total;
if( a[cur].l < a[cur].r )
if( a[cur].sum != a[cur * 2].sum + a[cur * 2 + 1].sum )
{
total = a[cur * 2].sum + a[cur * 2 + 1].sum;
a[cur * 2].sum += ( a[cur].sum - total ) / ( a[cur].r - a[cur].l + 1 ) * ( a[cur * 2].r - a[cur * 2].l + 1 );
a[cur * 2 + 1].sum += ( a[cur].sum - total ) / ( a[cur].r - a[cur].l + 1 ) * ( a[cur * 2 + 1].r - a[cur * 2 + 1].l + 1 );
}
if( l == a[cur].l && r == a[cur].r )
{
a[cur].sum += delta * ( a[cur].r - a[cur].l + 1 );
return ;
}
else
{
if( r <= mid ) insert( l , r , cur * 2 , delta );
else if( l > mid ) insert( l , r , cur * 2 + 1 , delta );
else
{
insert( l , mid , cur * 2 , delta );
insert( mid + 1 , r , cur * 2 + 1 , delta );
}
a[cur].sum = a[cur * 2].sum + a[cur * 2 + 1].sum;
}
}
long long
que( long long l , long long r , long long cur )
{
long long mid = ( a[cur].l + a[cur].r ) / 2;
long long total;
if( a[cur].l < a[cur].r )
if( a[cur].sum != a[cur * 2].sum + a[cur * 2 + 1].sum )
{
total = a[cur * 2].sum + a[cur * 2 + 1].sum;
a[cur * 2].sum += ( a[cur].sum - total ) / ( a[cur].r - a[cur].l + 1 ) * ( a[cur * 2].r - a[cur * 2].l + 1 );
a[cur * 2 + 1].sum += ( a[cur].sum - total ) / ( a[cur].r - a[cur].l + 1 ) * ( a[cur * 2 + 1].r - a[cur * 2 + 1].l + 1 );
}
if( l == a[cur].l && r == a[cur].r )
return a[cur].sum;
if( r <= mid )
return que( l , r , cur * 2 );
else if( l > mid )
return que( l , r , cur * 2 + 1 );
else
return que( l , mid , cur * 2 ) + que( mid + 1 , r , cur * 2 + 1 );
}
int main()
{
cin >> n >> q;
for( long long i = 1 ; i <= n ; i ++ )
{
scanf( "%I64d" , &s[i] );
s[i] += s[i - 1];
}
set( 1 , n , 1 );
for( long long i = 1 ; i <= q ; i ++ )
{
scanf( "%s" , ch );
if( ch[0] == 'Q' )
{
scanf( "%I64d%I64d" , &A , &B );
printf( "%I64d\n" , s[B] - s[A - 1] + que( A , B , 1 ) );
}
else
{
scanf( "%I64d%I64d%I64d" , &A , &B , &C );
insert( A , B , 1 , C );
}
}
return 0;
}
没有合适的资源?快使用搜索试试~ 我知道了~
POJ上一些已经AC的代码
共37个文件
cpp:37个
5星 · 超过95%的资源 需积分: 15 30 下载量 86 浏览量
2009-03-21
15:05:23
上传
评论
收藏 17KB RAR 举报
温馨提示
acm.pku.edu.cn/OnlineJudge上一些已经通过的代码
资源推荐
资源详情
资源评论
收起资源包目录
POJ.rar (37个子文件)
POJ
POJ 1001.cpp 1KB
POJ 2287.cpp 2KB
POJ 2309.cpp 1KB
POJ 2173.cpp 946B
POJ 1002.cpp 2KB
POJ 2479.cpp 636B
POJ 1067.cpp 396B
POJ 1011.cpp 1KB
POJ 2081.cpp 935B
POJ 2239.cpp 895B
POJ 3468.cpp 3KB
POJ 1195.cpp 1KB
POJ 1013.cpp 2KB
POJ 1163.cpp 852B
POJ 2533.cpp 637B
POJ 1006.cpp 825B
POJ 1274.cpp 912B
POJ 1007.cpp 1015B
POJ 2195.cpp 2KB
POJ 1094.cpp 2KB
POJ 1028.cpp 1KB
POJ 2291.cpp 394B
POJ 1000.cpp 104B
POJ 1005.cpp 406B
POJ 1004.cpp 248B
POJ 1088.cpp 977B
POJ 1012.cpp 373B
POJ 1469.cpp 1KB
POJ 1631.cpp 793B
POJ 1166.cpp 2KB
POJ 1159.cpp 548B
POJ 1068.cpp 1011B
POJ 1953.cpp 473B
POJ 1062.cpp 2KB
POJ 2196.cpp 1000B
POJ 1273.cpp 1KB
POJ 1003.cpp 608B
共 37 条
- 1
资源评论
- string02013-01-24非常感谢,是北大ACm在线提交系统上的代码。。
huo53926
- 粉丝: 2
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功