块状链表

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165

#include<stdio.h>#include<string.h>#include<math.h>#define maxc 1000000 //数列的最大长度int C; //数列的长度int val[maxc]; //数列中的每个元素struct NODE { //每个元素为链表中的一个节点 int next; //链表的下一节点 int jump; //链表的下sqrt(N)个节点 long long sum; //链表中以这个节点开始的连续sqrt(N)个节点的和};NODE list[maxc]; //链表的每个节点struct LIST { //连续段 int head; //连续段的起点 int len; //连续段的长度};int J; //保存sqrt(N)的值LIST l; //整个链表看作一个连续段void init() { //初始化函数 J = sqrt(C); //计算sqrt(N)的值 if (J<1) J=1; //最少为1 int i; for (i=0;i<C;i++){ //初始化链表 //链表的下一元素指针 if(i<C-1) list[i].next=i+1; else list[i].next=-1; //链表的下J元素指针 if(i<=C-J) list[i].jump=i+J; else list[i].jump=-1; list[i].sum = 0; //清空和为0 } long long k; for(i=0,k=0;i<J;i++)k+=val[i]; //计算前J项和 for(i=0;i<C-J;i++){ //计算每个数之后的连续J项和 list[i].sum = k; //从前一个连续J项和，减去第一项，加上最后一项，得到新的连续J项和 k = k - val[i] + val[i+J]; } list[i].sum = k; l.head = 0; //初始连续段的起点 l.len = C; //初始连续段的长段}int getlocate(LIST l, int t) //求连续段的第t个元素的位置{ if(t<0 || t>=l.len) return -1; //输入位置不合法 int i; i = l.head; while(t>=J){ //还有超过J个元素 i = list[i].jump; //直接跳过J个元素 t -= J; } while(t){ //不超过J个元素 i = list[i].next; //超过1个元素 t --; } return i; //返加元素所在位置}LIST merge(LIST a, LIST b){ //数列合并 if(a.len==0) return b; //a数列为空时返回b数列 if(b.len==0) return a; //b数列为空时返回a数列 int ha, hb, ia, ib, i,j; i = getlocate(a, a.len-1); //找到a数列最后一个元素 list[i].next = b.head; //指向b数列的第一个元素 LIST re;re.head=a.head, re.len=a.len+b.len; //合并后的数列 if(re.len<J) return re; //数列长度小于J，则不需要改变指针和连续段和 if(a.len<J){ //a的长度小于J，则改变指针要从a的第一个元素开始 ia = 0; //a的第一个元素 ib = J-a.len; //对应的J个元素后所在的位置 } else { //a的长度不小于J ia = a.len - J; //从a的倒数第J个元素开始 ib = 0; //从b的第一个元素开始 } ha = getlocate(a, ia); //求出第一个元素所在位置 hb = getlocate(b, ib); //求出最后一个元素所在位置 long long k; //连续J个元素的和 for(i=k=0,j=ha;i<J;i++,j=list[j].next) k+=val[j]; while(ia<a.len && ib<=b.len){ //枚举所有需要改变的节点 list[ha].jump = hb; //修改跳过J个元素的指针 list[ha].sum = k; //修改连续J个元素的和 k -= val[ha]; //减去第一个元素 if(hb!=-1) k += val[hb]; //加上最后一个元素 ha = list[ha].next; //第一个元素的下一节点 hb = list[hb].next; //最后一个元素的下一节点 ia++, ib++; //下一个连续J个元素 } return re; //返回合并后的数列}void move(int sa, int sb, int np){ //移动一段连续数列 int leftpartlen; //左边部分的元素个数 if(np<sa)leftpartlen=np+1; //移动段在插入位置的右边 else leftpartlen=np+1-(sb-sa+1);//移动段在插入位置的左边 LIST left, mid, right; //初始段分成三段 left.head = l.head; //左段的起始位置 left.len = sa; //左段的长度 mid.head = getlocate(l, sa); //中段的起始位置 mid.len = sb-sa+1; //中段的长度 right.head = getlocate(l, sb+1);//右段的起始位置 right.len = C-sb-1; //右段的长度 l = merge(left, right); //合并左右段 //在插入位置分成两段 left.head = l.head; //左段起始位置 left.len = leftpartlen; //左段长度 right.head = getlocate(l, leftpartlen);//右段起始位置 right.len = l.len - leftpartlen;//右段长度 l = merge(left, mid); //合并左段和中段 l = merge(l, right); //合并右段}void sum(int sa, int sb){ //求连续段的和 int i,t; long long ans = 0; //初始化和为0 i = getlocate(l,sa); //起始元素位置 t = sb-sa+1; //连续段长度 while(t>=J){ //超过J个元素 ans += list[i].sum; //一次累加连续J个元素的和 i = list[i].jump; //跳过J个元素 t -= J; } while(t){ //不足J个元素 ans += val[i]; //累加一个元素 i = list[i].next; //跳过一个元素 t --; } printf("%I64d\n", ans); //输出答案}int main() { int cs; scanf("%d",&cs); //输入数据组数 while(cs--){ scanf("%d",&C); //输入数列长度 int i,j; for(i=0;i<C;i++)scanf("%d",&val[i]); //输入每个元素 init(); //初始化 int S, sa, sb, np; scanf("%d",&S); //输入操作数 char st[30]; for(i=0;i<S;i++){ scanf("%s",st); if(strcmp(st,"Move")==0){//如果是移动操作 scanf("%d%d%d",&sa,&sb,&np); sa--,sb--,np--; move(sa,sb,np); //调用移动操作函数 } else if(strcmp(st,"Sum")==0){//如果是求和操作 scanf("%d%d",&sa,&sb); sa--,sb--; sum(sa,sb); //调用求和操作函数 } } } return 0;}