| 记录编号 |
159887 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
马拉松 |
最终得分 |
100 |
| 用户昵称 |
 wolf. |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.990 s |
| 提交时间 |
2015-04-22 22:34:58 |
内存使用 |
0.28 MiB |
显示代码纯文本
#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk=" ";
ofstream nnew("marathona.in",ios::app);
ifstream fin("marathona.in");
#define fout cout
#define Endl endl
#else
ifstream fin("marathona.in");
ofstream fout("marathona.out");
#endif
class node{//储存原始数据的类
public:
int x,y;
node(){
}
node(int a,int b){
x=a;
y=b;
}
};
class llink{//线段树类
public:
int l,r,di;
llink(){
di=999999999;
}
};
vector<llink> TT;//线段树
vector<int> num;//树状数组
vector<node> PP;//原始数据
int calc(int x1,int y1,int x2,int y2){//距离公式
return abs(x1-x2)+abs(y1-y2);
}
////////////////////////////////////树状数组
int lowbit(int n){//树状数组公式
return n&(-n);
}
void _add(int p,int n){//在p位加上n值
for(int i=p;i<num.size();i+=lowbit(i)){
num[i]+=n;
}
}
long long _sum(int n){//求前n项和
long long ans=0;
for(int i=n;i>0;i-=lowbit(i)){
ans+=num[i];
}
return ans;
}
int sum(int a,int b){//求区间a到b的和
if(a>b){
swap(a,b);
}
long long ans=0;
ans=_sum(b);
ans-=_sum(a);
return ans;
}
void rewrite_len(int p,int x,int y){//利用差分维护更新树状数组 并修改数据
int older,newer;
if(p!=0){//不是左顶点
older=sum(p-1,p);
newer=calc(PP[p-1].x,PP[p-1].y,x,y);
_add(p,newer-older);
}
if(p!=PP.size()-1){
//不是右顶点
older=sum(p,p+1);
newer=calc(PP[p+1].x,PP[p+1].y,x,y);
_add(p+1,newer-older);
}
PP[p].x=x;
PP[p].y=y;
}
////////////////////////////////////线段树
//线段树用来表示一段区间中，去掉区间中的某个点能使路径减少最多
void update(int it,int p,int n){//将p点的差分数值更新为n
if(TT[it].l==TT[it].r){
TT[it].di=n;
return;
}
int mid=(TT[it].l+TT[it].r)/2;
if(p<=mid){
update(2*it,p,n);
}else{
update(2*it+1,p,n);
}
TT[it].di=min(TT[it*2].di,TT[it*2+1].di);
}
void rewrite_tree(int p){//重新计算p点的差分值
if(p==0||p==PP.size()-1){
update(1,p,0);
return;
}
int r,u;
r=sum(p-1,p+1);//原始数值
u=calc(PP[p-1].x,PP[p-1].y,PP[p+1].x,PP[p+1].y);//直接连接值
update(1,p,u-r);
}
///////////////////////////////////////生成
void write_tree(int p,int a,int b){//构造一颗线段树 不写入数据
TT[p].l=a;
TT[p].r=b;
if(a==b){
return;
}
int mid=(a+b)/2;
write_tree(2*p,a,mid);
write_tree(2*p+1,mid+1,b);
}
void build(int n){//根据PP生成树状数组和线段树
for(int i=1;i!=PP.size();++i){
_add(i,calc(PP[i].x,PP[i].y,PP[i-1].x,PP[i-1].y));
}
write_tree(1,0,n-1);
for(int i=0;i!=PP.size();++i){
rewrite_tree(i);
}
}
///////////////////////////////////////维护
int find_tree(int p,int a,int b){//查找区间a b中的最小差分数
if(a>b){
return 0;
}
if(TT[p].l==a&&TT[p].r==b){
return TT[p].di;
}
int mid=(TT[p].l+TT[p].r)/2;
if(b<=mid){
return find_tree(2*p,a,b);
}else if(a>mid){
return find_tree(2*p+1,a,b);
}else{
return min(find_tree(2*p,a,mid),find_tree(2*p+1,mid+1,b));
}
}
void rebuild(int p,int x,int y){//修改一个点
rewrite_len(p,x,y);
rewrite_tree(p-1);
rewrite_tree(p);
rewrite_tree(p+1);
#if defined wolf
for(int i=1;i!=PP.size();++i){
cout<<sum(i-1,i)<<" ";
}cout<<endl;
for(int i=0;i!=PP.size();++i){
cout<<find_tree(1,i,i)<<" ";
}cout<<endl;
#endif
}
int find_sum(int a,int b){//查询一个区间
int ans=sum(a,b);//计算原始值
ans+=find_tree(1,a+1,b-1);//计算能减少的部分
return ans;
}
///////////////////////////////////////
int main(){
double n,q;
fin>>n>>q;
for(int i=0;i!=n;++i){
int a,b;
fin>>a>>b;
PP.push_back(node(a,b));
}
//读入完成
TT.resize((int)(n*(log(n)/log(2.0)))+5);
num.resize((int)n+5,0);
build((int)n);
//构造完成
#if defined wolf
for(int i=1;i!=PP.size();++i){
cout<<sum(i-1,i)<<" ";
}cout<<endl;
for(int i=0;i!=TT.size();++i){
if(TT[i].di==999999999){
continue;
}
cout<<TT[i].l<<kk<<TT[i].r<<kk<<TT[i].di<<endl;
//cout<<find_tree(1,i-1,i)<<" ";
}cout<<endl;
#endif
for(int i=0;i!=q;++i){
char t;
fin>>t;
if(t=='U'){
int a,b,c;
fin>>a>>b>>c;
rebuild(a-1,b,c);//修改一个点
}else{
int a,b;
fin>>a>>b;
fout<<find_sum(a-1,b-1)<<endl;//查询一个点
}
}
//-------------------------*/
#if defined wolf
cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
#endif
return 0;
}
//Designed by wolf
//Wed Apr 22 2015