首页 > 代码库 > HDU 1166 敌兵布阵

HDU 1166 敌兵布阵

2024-07-16 03:53:04   222人阅读

线段树。。。

数组开2*n 居然不够。。。手动写出线段树后才发现可能会超出2*n 个数。一直找不到错在哪，wa到哭，当时就想，一个点修改线段树居然wa成这样，简直不要不要的了

 

 ps：hdu1754 I Hate It 也是这样写的，输入输出形式稍微改下，和改为最大值

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn =200005; 7 const int INF =1000000009; 8  9 long long tree[maxn*2];10 long long ans;11 12 void update (int o,int l,int r,int p,int v){13     int m=l+(r-l)/2,lc=o<<1,rc=(o<<1)+1;14     if (l==r){15         tree[o]+=v;16     }17     else{18         if (p<=m) update (lc,l,m,p,v);19         if (p>m) update (rc,m+1,r,p,v);20         tree[o]=tree[lc]+tree[rc];21     }22 }23 24 void query (int o,int l,int r,int x,int y){25     if (x<=l&&r<=y){26         ans+=tree[o];27     }28     else {29         int m=l+(r-l)/2,lc=o<<1,rc=(o<<1)+1;30         if (x<=m) query (lc,l,m,x,y);31         if (m<y) query (rc,m+1,r,x,y);32     }33 }34 35 int main (){36     int n,q;37     int a,b;38     int t;39     scanf ("%d",&t);40     int kase=0;41     while (t--){42         scanf ("%d",&n);43         memset (tree,0,sizeof tree);　　//开始是写的 for (int i=1;i<=2*n)  wa成狗。。。44         for (int i=1;i<=n;i++){45             scanf ("%d",&b);46             update (1,1,n,i,b);47         }48         printf ("Case %d:\n",++kase);49             char c[10];50         while (~scanf ("%s",c)){51             if (c[0]==‘E‘)52                 break ;53             scanf ("%d%d",&a,&b);54             if (c[0]==‘A‘)55                 update (1,1,n,a,b);56             else if (c[0]==‘S‘)57                 update (1,1,n,a,-b);58             else {59                 ans=0;60                 query (1,1,n,a,b);//for (int i=1;i<=3*n;i++) cout<<tree[i]<<" ";61                 printf ("%I64d\n",ans);62             }63         }64     }65     return 0;66 }

 


联系
我们