【题解】LuoGu3948：数据结构

原题传送门
由于本题题面要复制的话比较麻烦，我就不copy了~~~
【题解】
首先两个操作：区间修改，区间查询
看到n<=80000 opt<=1000000就有点方了，此题题如其名，需要用到线段树？
当然不用！我发现了“你的询问操作不会超过1000次”
说明什么？询问可以暴力跑一遍，时间复杂度O(1000n)在承受范围内
那么修改呢？差分。我们只需用delta[i]表示a[i]-a[i-1]，对于[l,r] +x，就delta[l]+=x,delta[r+1]-=x，那么a[i]=sigma(delta[j])(1<=j<=i)

对于最后的一大堆询问，期望用O(1)完成每个询问，那么用前缀和预处理先跑一遍就可以了

注意：开int64(long long)

Code：

var
    delta,sum:array[0..1000000] of int64;
    ch,kongge:char;
    s,opt,mo,min,max,ans,final,x,y,z,n:int64;
    i,j:longint;

begin
    readln(n,opt,mo,min,max);
    for i := 1 to opt do
    begin
        read(ch,kongge);
        if ch = 'A' then
        begin
            readln(x,y,z);
            delta[x] := delta[x] + z;
            delta[y+1] := delta[y+1] - z;
        end else
        begin
            readln(x,y);
            s := 0;
            ans := 0;
            for j := 1 to y do
            begin
                s := s + delta[j];
                if (j >= x) and (s * j mod mo >= min) and (s * j mod mo <=max) then
                    inc(ans);
            end;
            writeln(ans);
        end;
    end;
    s := 0;
    for i := 1 to n do
    begin
        s := s + delta[i];
        sum[i] := sum[i-1];
        if (s * i mod mo >= min) and (s * i mod mo <= max) then inc(sum[i]);
    end;
    readln(final);
    for i := 1 to final do
    begin
        readln(x,y);
        writeln(sum[y] - sum[x-1]);
    end;
end.