1. 题目

传送门= ̄ω ̄=

给你N个数,有两种操作

1:给区间[a,b]内的所有数都增加X

2:询问区间[a,b]能被7整除的个数

2. 题解

对于线段树的每个节点,搞个数组d,d[i]表示在这个节点表示的区间内,对7取余等于i的数字有几个。
那么每次区间加x就是把数组d向后移动x mod 7位(环形移动,即0->1->2->3->4->5->6->0->1…)

询问的话,答案就是对应的d[0]的和

代码:

#include <bits/stdc++.h>
using namespace std;
struct N
{
    int l,r,f,d[10];N*s[2];
    N(){l=r=f=0,s[0]=s[1]=0,memset(d,0,sizeof(d));}
}*root=0;
void update(N*&a){for(int i=0;i<7;i++)a->d[i]=a->s[0]->d[i]+a->s[1]->d[i];}
void pdown(N*&a)
{
    int arr[10];
    for(int i=0;i<7;i++)arr[i]=a->s[0]->d[i];
    for(int i=0;i<7;i++)a->s[0]->d[(((i+a->f)%7)+7)%7]=arr[i];
    for(int i=0;i<7;i++)arr[i]=a->s[1]->d[i];
    for(int i=0;i<7;i++)a->s[1]->d[(((i+a->f)%7)+7)%7]=arr[i];
    a->s[0]->f+=a->f,a->s[1]->f+=a->f,a->f=0;
}
void build(int l,int r,N*&a)
{
    a=new N,a->l=l,a->r=r;
    if(l==r){int k;scanf("%d",&k),a->d[((k%7)+7)%7]=1;return;}
    build(l,(l+r)>>1,a->s[0]),build(((l+r)>>1)+1,r,a->s[1]),update(a);
}
void change(int l,int r,int k,N*&a)
{
    if(l<=a->l&&a->r<=r)
    {
        int arr[10];
        for(int i=0;i<7;i++)arr[i]=a->d[i];
        for(int i=0;i<7;i++)a->d[(((i+k)%7)+7)%7]=arr[i];
        a->f+=k;return;
    }
    if(a->f)pdown(a);
    if(l<=((a->l+a->r)>>1))change(l,r,k,a->s[0]);
    if(r>((a->l+a->r)>>1))change(l,r,k,a->s[1]);
    update(a);
}
int query(int l,int r,N*&a)
{
    if(l<=a->l&&a->r<=r)return a->d[0];
    if(a->f)pdown(a);
    int tot=0;
    if(l<=((a->l+a->r)>>1))tot+=query(l,r,a->s[0]);
    if(r>((a->l+a->r)>>1))tot+=query(l,r,a->s[1]);
    return tot;
}
int n,q;
char opt[10];
int main()
{
    scanf("%d",&n),build(1,n,root),scanf("%d",&q);
    for(int i=1,a,b,c;i<=q;i++)
    {
        scanf("%s%d%d",opt,&a,&b);
        if(!strcmp(opt,"add"))scanf("%d",&c),change(a,b,c,root);
        else printf("%d\n",query(a,b,root));
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *