hdoj 4267 - 线段树

2012长春赛区网络赛。。。A题

http://acm.hdu.edu.cn/showproblem.php?pid=4267

什么都不说了，贴代码。。。郁闷。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int N=50002;
int n, m;
struct node
{
bool flag;
int l, r;
int val;
int add[55];
void reset()
{
memset(add, 0, sizeof(add));
flag = false;
}
} a[N*4];
int b[N], kk, cc;
void build(int l, int r, int p)
{
a[p].l = l;
a[p].r = r;
a[p].reset();
if(l==r)
{
a[p].val = b[l];
return;
}
int mid = (l+r)>>1;
build(l, mid, p*2);
build(mid+1, r, p*2+1);
}
inline int ijToNum(int i, int j)
{
return (i*(i+1))/2 + j;
}
inline void down(int p)
{
if (a[p].flag == true)
{
int i, j;
for (i = 0; i < 10; i++)
{
int ii = i+1;
for (j = 0; j <= i; j++)
{
if (a[p].add[ijToNum(i, j)] != 0)
{
a[p*2].add[ijToNum(i, j)] += a[p].add[ijToNum(i, j)];
a[p*2].flag = true;
a[p*2+1].add[ijToNum(i, (ii*50001-(a[p*2].r-a[p*2].l+1-j) % ii ) % ii )] += a[p].add[ijToNum(i, j)];
//这里一定要注意左半部分已经产生的偏移对后半部分的影响。。。即j的用处。。。
a[p*2+1].flag = true;
}
}
}
a[p].reset();
}
}
void update(int l, int r, int p, int ki)
{
if(a[p].l==l && a[p].r==r)
{
//a[p].add[kk-1][ki] += cc;
a[p].add[ijToNum(kk-1, ki)] += cc;
a[p].flag = true;
return;
}
//down(p);
int mid = (a[p].l+a[p].r)>>1;
if(r<=mid)
update(l, r, p*2, ki);
else if(l>mid)
update(l, r, p*2+1, ki);
else
{
update(l, mid, p*2, ki);
update(mid+1, r, p*2+1, (kk*50001-(mid-l+1-ki)%kk)%kk ); //这里开始搞成a[p].r - a[p].l + 1了。。。。
}
}
int query(int l, int r, int p)
{
if(a[p].l==l && a[p].r==r)
{
if (a[p].flag == true)
{
for (int i = 0; i < 10; i++)
{
//a[p].val += a[p].add[i][0];
a[p].val += a[p].add[ijToNum(i, 0)];
//a[p].add[i][0] = 0;
a[p].add[ijToNum(i, 0)] = 0;
}
a[p].flag = false;
}
return a[p].val;
}
down(p);
int mid = (a[p].l+a[p].r)>>1;
if(r<=mid)
return query(l, r, p*2);
else if(l>mid)
return query(l, r, p*2+1);
}
int main()
{
int op, aa, bb;
while(scanf("%d", &n)!=EOF)
{
for (int i = 1; i <= n; i++)
{
scanf("%d", &b[i]);
}
build(1, n, 1);
scanf("%d", &m);
//printf("Case #%d:n", cas1++);
while(m--)
{
scanf("%d", &op);
if (op == 1)
{
scanf("%d %d %d %d", &aa, &bb, &kk, &cc);
update(aa, bb, 1, 0);
}
else
{
scanf("%d", &aa);
printf("%dn", query(aa, aa, 1));
}
}
}
return 0;
}

最后

以上就是甜美香菇为你收集整理的hdoj 4267 - 线段树的全部内容，希望文章能够帮你解决hdoj 4267 - 线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。