C~F Java题解，代码已去除冗余~~~

C 小红的数组查询（二）

p为1的时候需要特判，否则数列的周期为p/gcd(p,d)，时间复杂度O(q+log(pd))

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int d=sc.nextInt(),p=sc.nextInt(),gcd=p/gcd(p,d);
        for(int i=sc.nextInt();i!=0;i--){
            long l=sc.nextLong(),r=sc.nextLong();
            System.out.println(p==1?(l==1?(r==1?1:2):1):Math.min(r-l+1,gcd));
        }
    }
    static int gcd(int a,int b){
        return a<b?gcd(b,a):b==0?a:gcd(a%b,b);
    }
}

D 小红的区间修改（一）

需要记录下每个区间发范围，而每次操作后的答案即为历次可进行的操作的最大区间长度加1，在实现上用了有序映射，时间复杂度O(qlogq)

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        TreeMap<Integer,Integer> map=new TreeMap<>();
        map.put(0,0);
        map.put((int)1e6,(int)1e6);
        int ans=0;
        for(int i=Integer.parseInt(bf.readLine());i!=0;i--){
            StringTokenizer st=new StringTokenizer(bf.readLine());
            int l=Integer.parseInt(st.nextToken()),r=Integer.parseInt(st.nextToken());
            if(map.get(map.floorKey(l))<l&&map.ceilingKey(l)>r){
                ans=Math.max(ans,r-l+1);
                map.put(l,r);
            }
            bw.write(ans+1+"\n");
        }
        bw.flush();
    }
}

E 小红的数组操作

最佳方案一定是操作1和操作2各做一次（这里不妨将a[0]和a[n+1]都定为0，其操作代价为0，以不失一般性），需要在固定每个操作1位置的前提下，双指针寻找最长的合法数组，而此时的操作二即为前缀操作2的最最小值，时间复杂度O(n)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),a[]=new int[n+5];
        long pre[]=new long[n+5],ans=(long)1e18;
        pre[0]=(long)1e18;
        for(int i=1;i<=n;i++){
            a[i]=sc.nextInt();
            pre[i]=Math.min(pre[i-1],(long)a[i]*(n-i+1));
        }
        Set<Integer> set=new HashSet<>();
        for(int i=0,j=1;i<=n;i++){
            set.remove(a[i]);
            while(true){
                if(j>n||set.contains(a[j])){
                    ans=Math.min(ans,(long)a[i]*i+pre[j]);
                    break;
                }
                else{
                    set.add(a[j++]);
                }
            }
        }
        System.out.println(ans);
    }
}

F 小红的区间修改（二）

利用有序映射记录每一段的数字填充情况，同事记录每种数字的段数，每次操作次数之和最多添加或者删除q段区间，时间复杂度O(qlogq)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        TreeMap<Integer,int[]> map1=new TreeMap<>();
        Map<Integer,Integer> map2=new HashMap<>();
        map1.put(0,new int[]{0,0});
        map1.put((int)1e6,new int[]{(int)1e6,0});
        for(int i=sc.nextInt();i!=0;i--){
            int l=sc.nextInt(),r=sc.nextInt(),x=sc.nextInt(),pre=map1.lowerKey(l);
            //先计算前边覆盖的部分
            if(pre<l){
                int cur[]=map1.get(pre);
                if(cur[0]<=r&&cur[0]>=l){
                    map1.put(pre,new int[]{l-1,cur[1]});
                }
                else if(cur[0]>r){
                    map1.put(pre,new int[]{l-1,cur[1]});
                    map1.put(r+1,new int[]{cur[0],cur[1]});
                    inc(map2,cur[1],1);
                }
            }
            //计算后边的部分
            for(int j=map1.ceilingKey(l);j<=r;j=map1.higherKey(j)){
                int cur[]=map1.get(j);
                if(cur[0]<=r){
                    map1.remove(j);
                    inc(map2,cur[1],-1);
                }
                else{
                    map1.remove(j);
                    map1.put(r+1,new int[]{cur[0],cur[1]});
                }
            }
            map1.put(l,new int[]{r,x});
            inc(map2,x,1);
            System.out.println(map2.size()+1);
        }
    }
    static void inc(Map<Integer,Integer> map,int a,int b){
        map.put(a,map.getOrDefault(a,0)+b);
        if(map.get(a)==0){
            map.remove(a);
        }
    }
}