| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求教为什么我用 c++ 提交了几十遍都是 WA,
然后改用g++ 试一下却神奇般的 AC了。
#include<iostream>
using namespace std;
#include<stdlib.h>
#include<stdio.h>
typedef long long int int64;
typedef struct node
{
int a,b;
//long long value,bj;
int64 value;
int64 bj;
int left,right;
}node;
node nodes[410000];
void create(int &num,int a,int b)
{
int ji=num;
nodes[ji].a=a;
nodes[ji].b=b;
nodes[ji].bj=0;
nodes[ji].value=0;
if(a<(b-1))
{
num++;
nodes[ji].left=num;
create(num,a,(a+b)/2);
num++;
nodes[ji].right=num;
create(num,(a+b)/2,b);
}
else
{
nodes[ji].left=-1;
nodes[ji].right=-1;
}
}
void clear(int num)
{
int a,b;
if(nodes[num].bj!=0)
{
nodes[num].value+=(nodes[num].b-nodes[num].a)*nodes[num].bj;
a=nodes[num].left;
b=nodes[num].right;
if(a!=-1&&b!=-1)
{
//if(nodes[a].bj!=0)clear(a);
//if(nodes[b].bj!=0)clear(b);
nodes[a].bj+=nodes[num].bj;
nodes[b].bj+=nodes[num].bj;
}
nodes[num].bj=0;
}
}
void insert(int num,int c,int d,int64 z)
{
int a,b;
if(nodes[num].bj!=0)clear(num);
if(c<=nodes[num].a&&d>=nodes[num].b)
{
nodes[num].value+=(int64)(nodes[num].b-nodes[num].a)*z;
a=nodes[num].left;
b=nodes[num].right;
if(a!=-1&&b!=-1)
{
//clear(a);
//clear(b);
nodes[a].bj+=z;
nodes[b].bj+=z;
}
}
else
{
if(c<(nodes[num].a+nodes[num].b)/2)insert(nodes[num].left,c,d,z);
else clear(nodes[num].left);
if(d>(nodes[num].a+nodes[num].b)/2)insert(nodes[num].right,c,d,z);
else clear(nodes[num].right);
a=nodes[num].left;
b=nodes[num].right;
nodes[num].value=nodes[a].value+nodes[b].value;
}
}
int64 query(int num,int c,int d)
{
if(nodes[num].bj!=0)clear(num);
if(c<=nodes[num].a&&d>=nodes[num].b)return nodes[num].value;
else if(c>=(nodes[num].a+nodes[num].b)/2) return query(nodes[num].right,c,d);
else if(d<=(nodes[num].a+nodes[num].b)/2) return query(nodes[num].left,c,d);
else
{
//long long a,b;
int64 a,b;
a=query(nodes[num].right,c,d);
b=query(nodes[num].left,c,d);
return a+b;
}
}
int main()
{
//freopen("asimple.in","r",stdin);
//freopen("asimple.out","w",stdout);
int n,q,i,a,b,num=0;
//long long ab;
int64 ab;
char ch;
//cin>>n>>q;
scanf("%d%d",&n,&q);
create(num,0,n);
for(i=0;i<n;i++)
{
scanf("%lld",&ab);
insert(0,i,i+1,ab);
}
while(q--)
{
//cin>>ch;
scanf("%s",&ch);
switch(ch)
{
case 'C':
{
//cin>>a>>b>>c;
scanf("%d%d%lld",&a,&b,&ab);
insert(0,a-1,b,ab);
}break;
case 'Q':
{
//cin>>a>>b;
scanf("%d%d",&a,&b);
//cout<<query(0,a-1,b)<<endl;
printf("%lld\n",query(0,a-1,b));
}
break;
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator