首页 > 代码库 > 【stoi】2010 国王
【stoi】2010 国王
测评的一天...
放道学校测评（stoi2010某题）题解吧...
嗯，就是这么无聊...
这是T3...
（嗯，T2的高精度和T4的拓扑排序我都不会）...
题目：
网址：没有...
大意：区间加法，求各个数
嗯，看到区间，又是T3，肯定是线段树...
再看数据范围——
...
线段树便开始打了起来...
其实也只是区间求和...
思路：线段树区间加法，然后输出时全部扫一遍，遇到根结点输出
代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int sum[800000]={0},add[800000]={0};//嗯，数组开大些 5 void xiugai(int rt){ 6 sum[rt]=sum[rt*2]+sum[rt*2+1]; 7 } 8 void biaoji(int l,int r,int rt){ 9 if(add[rt]){ 10 add[rt*2]+=add[rt]; 11 add[rt*2+1]+=add[rt]; 12 sum[rt*2]+=add[rt]*l; 13 sum[rt*2+1]+=add[rt]*r; 14 add[rt]=0; 15 } 16 } 17 void jia(int x,int y,int c,int l,int r,int rt){ 18 if(x<=l&&r<=y){ 19 sum[rt]+=(r-l+1)*c; 20 add[rt]+=c; 21 return ; 22 } 23 int m=(l+r)/2; 24 if(x<=m)jia(x,y,c,l,m,rt*2); 25 if(m<y)jia(x,y,c,m+1,r,rt*2+1); 26 xiugai(rt); 27 } 28 void out(int l,int r,int rt){ 29 if(l==r){//根结点 30 printf("%d ",sum[rt]); 31 return ; 32 } 33 int m=(l+r)/2; 34 biaoji(l-m+1,r-m,rt); 35 out(l,m,rt*2); 36 out(m+1,r,rt*2+1); 37 } 38 int main(){ 39 int n,m,b,c,cc,ccc; 40 scanf("%d%d",&n,&m); 41 for(b=0;b<m;b++){ 42 scanf("%d%d%d",&c,&cc,&ccc);//区间加法 43 jia(c,cc,ccc,1,n,1); 44 } 45 out(1,n,1);//访问各个根结点逐个输出 46 }
就这样提交上去了...
嗯，A了...
线段树裸题...
然而正解...
是另外一种神奇解法...
有点前缀和思想...
copy一下解题报告——
说到二重过不了，然而还能捞60分...
其实主要思路就是前缀和...
学老师一样画张图吧（当然不会手画）...
首先呢，整个序列都是0
假设下n=5,m=2
第一次增加，1~3加上1，那么根据报告的解法，a[1]+=1,a[4]-=1,也就是得到了那一段序列，而在之后的操作中，是第n个数=第n-1个数+a[n]（前缀和思想），因此就现在而论，第1个数是1，第2个数=第（2-1=）1个数+a[2]（=0）=1，以此类推，第三个数也会是1，而第4个数a[4]=-1，因此到了第4个数，就会=第（4-1=）3个数+a[4](-1)=0,所以第4个数就是0，第5个数也就会等于0（然而这都是针对第一次增加而言）
第二次增加，3~5加上2，那么还是a[3]+=2,a[6]-=2，因为第6个数不会弄到，因此不用管它，这样的话，就又是一段数列
最后，a[n]=a[n-1]+a[n],用sum代替a[n-1]...
来一重循环，一开始sum=0，a[1]=1，因此第一个数就是1，a[2]=0，因此第二个数也是1，a[3]=2，因此sum+=a[3],所以第三个数等于3，紧接着-1，+0，也就得到了最后的答案1 1 3 2 2
神奇解法的代码——
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int main(){ 5 int n,m,b,c,cc,ccc,sum=0,a[100001]={0}; 6 scanf("%d%d",&n,&m); 7 for(b=0;b<m;b++){ 8 scanf("%d%d%d",&c,&cc,&ccc); 9 a[c]+=ccc; 10 a[cc+1]-=ccc; 11 } 12 for(b=1;b<=n;b++){ 13 sum+=a[b]; 14 printf("%d ",sum); 15 } 16 }
嗯，和我又臭又长的代码形成强烈反差对比...
至于其他解法，嗯，本jr都不会...
又水了一篇博客...
【stoi】2010 国王