题目链接:Click here~~
题意:
给你一个数列{An},有两种操作:
1、将区间 [a,b] 中满足条件 (i-a)%k = 0 的点全部加 c。
2、询问某一点的值。
解题思路:
由于更新区间的时候更新的是一些离散的点,所以我们要想办法将这些离散的点转化成连续的点。
注意到 k 的范围很小(k<=10),分析一下可知,所有的更新可以根据 k 以及 a%k 分为1+2+3+…+10 = 55 种情况。
k 为 1 时:0、1、2、3……
k 为 2 时:0、2、4、6……
1、3、5、7……
k 为 3 时:……
于是,可以建55棵线段树,更新的时候根据 k 及 a%k 选取一棵进行更新,查询的时候需要将10棵的和(1<=k<=10)加起来得到结果。
细节方面,只要在更新和查询时把真实区间与每棵树的对应等价区间转化好即可。(开始时我就是这个地方错了,找了半天才找出错误)
然后就可以套模板AC啦拉啦。
#include <stdio.h>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)
typedef __int64 LL;
const int M = 50003;
int v[M];
struct Tnode
{
int l,r;
int sum,delta;
}TT[56][M<<2];
void Build(Tnode* T,int u,int l,int r)
{
T[u].l = l , T[u].r = r;
if(l == r-1)
{
T[u].sum = T[u].delta = 0;
return ;
}
int mid = MID(l,r);
Build(T,L(u),l,mid);
Build(T,R(u),mid,r);
T[u].sum = T[u].delta = 0;
}
void Updata(Tnode* T,int u,int l,int r,int up)
{
if(T[u].l == l && T[u].r == r)
{
T[u].delta += up;
return ;
}
else
T[u].sum += up*(r-l);
int mid = MID(T[u].l,T[u].r);
if(l >= mid)
Updata(T,R(u),l,r,up);
else
if(r <= mid)
Updata(T,L(u),l,r,up);
else
{
Updata(T,L(u),l,mid,up);
Updata(T,R(u),mid,r,up);
}
}
int Query(Tnode* T,int u,int l,int r)
{
int delta = T[u].delta;
if(T[u].l == l && T[u].r == r)
return T[u].sum + delta*(r-l);
T[L(u)].delta += delta;
T[R(u)].delta += delta;
T[u].sum += delta*(T[u].r-T[u].l);
T[u].delta = 0;
int mid = MID(T[u].l,T[u].r);
if(l >= mid)
return Query(T,R(u),l,r);
else
if(r <= mid)
return Query(T,L(u),l,r);
else
return Query(T,L(u),l,mid) + Query(T,R(u),mid,r);
}
int id(int a,int k) //返回要更新的是哪颗线段树
{
return k*(k-1)/2 + a%k +1;
}
int main()
{
int n,Q,cmd,a,b,k,t;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(k=1;k<=10;k++)
for(int i=0;i<k;i++)
Build(TT[id(i,k)],1,1/k,n/k+1);
scanf("%d",&Q);
while(Q--)
{
scanf("%d",&cmd);
if(cmd == 1)
{
scanf("%d%d%d%d",&a,&b,&k,&t);
Updata(TT[id(a,k)],1,a/k,a/k+(b-a)/k+1,t);
}
else
{
scanf("%d",&a);
int tmp = 0;
for(k=1;k<=10;k++)
tmp += Query(TT[id(a,k)],1,a/k,a/k+1);
printf("%d\n",tmp+v[a]);
}
}
}
return 0;
}
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
HDU 1022 Train Problem I 附详细思路
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
考试类精品--A simple SDK for HDU. 一个提供一卡通服务、考试、课表、选课和公共信息等 API
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
2-sat---hdu3062,代码详尽,清晰,格式规范,亲测无误。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
A simple SDK for HDU. hdu-api 是一个集结 HDU 所有教务管理服务的 SDK,提供了一卡通服务、考试、课表、选课和一些公共信息如空闲教室、上课时间等信息的 API。 hdu-api 主要基于 Requests 库和 Beautiful Soup 库...
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
算法-确定比赛名次(HDU-1285).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的