java_string

发表于 2024-04-11 更新于 2024-04-15 Disqus：

JAVA速成Day4——字符串

字符串也是ACM里常用的东西，但是java里的字符串我并不是很熟悉，所以这次就稍微速通一下~

String：

首先我们得清楚String类在java中是不可变的。这真的勾八坑爹

equals()

比较两个String是否相等，返回boolean

compareTo()

比较两个字符串的字典序，返回负数/0/正数

substring()

提取子串，左闭右开。第二个参数可选

1	"blackbird".substring(5) // bird

toCharArray()

转化为 Char[] 。

StringBuilder

由于String类部是 final 类型，不可变。因此当你使用 + 连接两个String时，事实上会再new一个String对象，这是没有效率的。

所以java提供了一个类StringBuilder，它是可变的。

public class Main {
    public static void main(String[] args) {
        StringBuilder str = new StringBuilder();
        str.append("i ").append("love ").append("blackbird.");
        String output = str.toString();
        System.out.println(output);
        str.setCharAt(0, 'u');
        System.out.println(str);
    }
}

顺带一提

这里提到了方法equals() 。事实上，对于所有非基本类型，都应该使用这个方法来判断对象之间是否相等。

基本类型	对应的引用类型
boolean	java.lang.Boolean
byte	java.lang.Byte
short	java.lang.Short
int	java.lang.Integer
long	java.lang.Long
float	java.lang.Float
double	java.lang.Double
char	java.lang.Character

例如int对应的引用类型Integer

java_interface

发表于 2024-04-10 更新于 2024-04-11 Disqus：

JAVA速成Day3——接口

java提倡OOP(面向对象编程)，然后有个东西叫做抽象类，需要子类继承来重写其定义的方法。

然后接口这个东西更抽象，相比抽象类，它只有方法，没有字段：

interface bird{
    void fly();
    String getName();
}

当具体的类要实现这些接口时，需要使用 implements 关键字：

class blackbird implements bird{
    private String name;

    public blackbird(String name){
        this.name = name;
    }

    @Override
    public void fly() {
        System.out.println(name + " is flying~");
    }

    @Override
    public String getName() {
        return name;
    }
}

然而，java不能同时继承多个类，但是可以同时实现多个接口。

接口之间可以继承：

interface Hello {
    void hello();
}

interface bird extends Hello {
    void fly();
    String getName();
}

神奇的是，可以通过接口去引用对象：

public class test {
    public static void main(String[] args) {
        bird bb = new blackbird("taffy");
        bb.fly();
    }
}

然而，对于对象自己实现的方法，接口没办法引用。

实际上，在我整的JAVA速成Day1那篇介绍集合的文章中，我留了个坑：用Map引用TreeMap。

实际上这里的Map，以及List，都是接口。

它们引用的对象，只能调用自己即继承的接口内部的方法。

因此对于TreeMap中独属于该类的方法，接口Map不能调用。因此你会发现IDEA的自动补全里少了点API。

另外，接口中可以定义 default 方法，然后直接在接口内部实现：

interface bird{
    void fly();
    String getName();

    default void hello(){
        System.out.println(getName() + " will succeed!");
    }
}

class blackbird implements bird{
    private String name;

    public blackbird(String name){
        this.name = name;
    }

    @Override
    public void fly() {
        System.out.println(name + " is flying~");
    }

    @Override
    public String getName() {
        return name;
    }

    public void hh(){

    }
}

public class test {
    public static void main(String[] args) {
        bird bb = new blackbird("blackbird");
        bb.hello();
    }
}

这样的话，如果对于一个接口新增一个方法，就不需要更改所有实现它的子类了，只需要在需要的地方 override 即可。

晚安

事实上接口是可以有字段的，但是其类型为 public static final ：

public interface Person {
    public static final int MALE = 1;
    public static final int FEMALE = 2;
}

--update 24.4.11

JAVA速成Day1——集合

发表于 2024-04-09 更新于 2024-05-01 Disqus：

JAVA速成Day1——集合

主要针对南京大学软件学院机试

1. List

分为ArrayList和LinkedList

ArrayList可以理解为C++ STL的vector（

LinkedList则为链表实现动态数组

import java.util.ArrayList;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        // 创建
        ArrayList<String> list = new ArrayList<>();
        // LinkedList<String> list = new LinkedList<>();
        
        // 添加
        list.add("blackbird");
        list.add("greybird");
        list.add("darkbird");

        // 获取第i个元素
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            System.out.println(s);
        }
        // 迭代器遍历的for each
        for (String s : list) {
            System.out.println(s);
        }
        // 删除元素，下标从0开始
        list.remove(1);
        for (String s : list) {
            System.out.println(s);
        }
        // 修改元素
        list.set(1, "yy");
        for (String s : list) {
            System.out.println(s);
        }
    }
}

2. 数组排序

一般的数组升序排序：（这里的话，是可以指定排序范围的

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
    int[] list = new int[110];
    int n;
    Scanner sc = new Scanner(System.in);
    void sol(){
        n = sc.nextInt();
        for(int i = 0; i < n; i++)
            list[i] = sc.nextInt();
        Arrays.sort(list, 0, n);
        for(int i = 0; i < n; i++)
            System.out.print(list[i] + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        // 创建
        Main Solution = new Main();
        Solution.sol();
    }
}

降序的话，是需要自定义一个 Comparator 类的。

但是无论是Array.sort还是Collections.sort都没办法同时指定 Comparator 和下标范围。因此这里使用动态数组可能更为方便：

import java.util.*;


public class Main {
    ArrayList<Integer> blackbird = new ArrayList<>();
    int n;
    Scanner sc = new Scanner(System.in);
    Comparator<Integer> cmp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            Integer val = o2 - o1;
            return val.intValue();
        }
    };
    void sol(){
        n = sc.nextInt();
        blackbird.clear();
        for(int i = 0; i < n; i++)
            blackbird.add(sc.nextInt());

        Collections.sort(blackbird, cmp);
        for(int i = 0; i < n; i++)
            System.out.print(blackbird.get(i) + " ");
        System.out.println();
    }
    public static void main(String[] args) {
        // 创建
        Main Solution = new Main();
        Solution.sol();
    }
}

对于 Comparator 类中，我们需要重写 compare 函数。如果参数一根据你想要的定义小于参数二，那么返回负整数。等于返回零。大于返回正整数。

另外，集合不支持 int 这种基本数据类型。需要使用对应的对象 Integer 。

3. 队列

在ACM里，队列的使用非常广泛，包括如下：

BFS
单调队列，处理滑动窗口模型
优先队列模拟堆

个人认为，在ACM场景中，一般使用 LinkedList 实现普通队列：

import java.util.*;


public class Main {
    // 创建队列
    Queue<String> q = new LinkedList<>();
    int n;
    Scanner sc = new Scanner(System.in);

    void sol(){
        // 添加元素
        q.offer("blackbird");
        q.offer("greybird");
        q.offer("darkbird");
        System.out.println(q);

        // 删除元素
        q.poll();
        System.out.println(q);

        // 队首
        System.out.println(q.peek());
        System.out.println(q.peek());

        // 队尾元素的话，Queue是不支持的，可能需要自己维护
    }
    public static void main(String[] args) {
        // 创建
        Main Solution = new Main();
        Solution.sol();
    }
}

关于优先队列，可能需要传入 Comparator 接口。这里我选择使用java来实现dijkstra+堆优化算法来作为示例：

import java.util.*;


public class Main {
    static final int N = 200010;
    static int n, m, S, used=0;
    static Scanner sc = new Scanner(System.in);
    static int[] head = new int[N>>1];
    static int[] point = new int[N<<1];
    static int[] nxt = new int[N<<1];
    static int[] val = new int[N<<1];
    static int[] dis = new int[N>>1];
    static boolean[] vis = new boolean[N>>1];

    static void add(int u, int v, int w){
        point[++used] = v;
        nxt[used] = head[u];
        head[u] = used;
        val[used] = w;
    }

    static class node{
        int u, d;
        node(){}
        node(int _u, int _dis){u = _u; d = _dis;}
    }

    static void Dijkstra(){
        Comparator<node> cmp = new Comparator<node>() {
            @Override
            public int compare(node o1, node o2) {
                return o1.d - o2.d;
            }
        };
        PriorityQueue<node> q = new PriorityQueue<>(cmp);
        q.add(new node(S, 0));
        while(!q.isEmpty()){
            node nn = q.poll();
            int u = nn.u, d = nn.d;
            if(vis[u]) continue;
            vis[u] = true;
            for(int k = head[u]; k > 0; k = nxt[k]){
                int v = point[k];
                if(!vis[v] && dis[v] > dis[u] + val[k]){
                    dis[v] = dis[u] + val[k];
                    q.add(new node(v, dis[v]));
                }
            }
        }
    }
    static void sol(){
        n = sc.nextInt(); m = sc.nextInt(); S = sc.nextInt();
        for(int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f;
        dis[S] = 0;
        for(int i = 1; i <= m; i++){
            int u, v, w;
            u = sc.nextInt(); v = sc.nextInt(); w = sc.nextInt();
            add(u, v, w);
            add(v, u, w);
        }
        Dijkstra();
        for(int i = 1; i <= n; i++){
            System.out.print(dis[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        sol();
    }
}

顺带一提，这玩意在洛谷上MLE了（

关于双端队列，同样采用 LinkedList 接口。

众所周知，单调队列通常使用双端队列实现，而单调队列的一个典型例子就是实现复杂度的多重背包：

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);
    static int[][] f = new int[2][N];
    static int n, V;

    static void sol(){
        n = sc.nextInt(); V = sc.nextInt();
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int ii = i & 1;
            int v, w, s;
            v = sc.nextInt(); w = sc.nextInt(); s = sc.nextInt();
            for(int j = 0; j < v; j++){
                Deque<Integer> q = new LinkedList<>();
                for(int k = j; k <= V; k += v){
                    while(!q.isEmpty() && k - q.peekFirst() > s * v) q.pollFirst();
                    while(!q.isEmpty() && f[ii^1][q.peekLast()] + (k - q.peekLast()) / v * w < f[ii^1][k])
                        q.pollLast();
                    q.addLast(k);
                    f[ii][k] = f[ii^1][q.peekFirst()] + (k - q.peekFirst()) / v * w;
                    ans = Math.max(ans, f[ii][k]);
                }
            }
        }
        System.out.println(ans);
    }
    public static void main(String[] args) {
        sol();
    }
}

可以把dp的式子转化一下，得到可以使用单调队列维护的形式。

4. Map

首先java中有 HashMap ，类似于C++中的unordered_map：

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);


    static void sol(){
        HashMap<Integer, String> hashmap = new HashMap<>();
        // 添加key-value pair
        hashmap.put(520, "blackbird");
        hashmap.put(1314, "love u, ");
        hashmap.put(114514, "acm-icpc");
        // 获取值
        System.out.println(hashmap.get(1314) + hashmap.get(520));
        // 修改
        hashmap.put(114514, "fwyy");
        System.out.println(hashmap.get(114514));
        // 遍历
        for(Integer key: hashmap.keySet()){
            System.out.println(key + " -> " + hashmap.get(key));
        }
    }
    public static void main(String[] args) {
        sol();
    }
}

但是我们要是想要个有序的map，可以使用 TreeMap ：

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);


    static void sol(){
        Comparator<Integer> cmp = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                Integer sub = o1 - o2;
                return sub.intValue();
            }
        };
        Map<Integer, String> map = new TreeMap<>(cmp);
        // 添加key-value pair
        map.put(520, "blackbird");
        map.put(1314, "love u, ");
        map.put(666, "acm-icpc");
        // 获取值
        Integer key1314 = 1314;
        System.out.println(map.get(1314) + map.get(520));
        // 修改
        map.put(114514, "fwyy");
        System.out.println(map.get(114514));
        // 遍历
        for(Integer key: map.keySet()){
            System.out.println(key + " -> " + map.get(key));
        }
        // 查看是否存在键值对
        if(map.containsKey(520)){
            System.out.println("!!!!");
        }
    }
    public static void main(String[] args) {
        sol();
    }
}

可以使用自定义的 Comparator 。

这里我给自己挖了个坑，直接使用 Map 来定义。欸，是不是感觉少了点API了呢？hh

update（24.4.15）：

方法 getOrDefault(key, v) 。寻找key，若不存在则返回v。（source：leetcode 49）

5. Set

这里我只想讲红黑树实现的 TreeSet ，毕竟在ACM里一般都把set当平衡树来用（什么）

这里就不拿 blackbird 什么的当例子了，有点草（

import java.util.*;


public class Main {
    static final int N = 20010;
    static Scanner sc = new Scanner(System.in);


    static void sol(){
        TreeSet<Integer> s = new TreeSet<>();
        s.add(1); s.add(3); s.add(1); s.add(4); s.add(5); s.add(2); s.add(0);
        s.add(2333);
        System.out.println(s.contains(114514));
        for(Integer num: s){
            System.out.print(num + " ");
        }
        System.out.println();
        // 小于等于
        System.out.println(s.floor(10)); // 5
        // 大于等于
        System.out.println(s.ceiling(4)); // 4
        // 小于
        System.out.println(s.lower(5)); // 4
        // 大于
        System.out.println(s.higher(5)); // 2333
        // 删除
        s.remove(2333);
        for(Integer num: s){
            System.out.print(num + " ");
        }
    }
    public static void main(String[] args) {
        sol();
    }
}

欸，那java里是否有像C++中 multiset 类似的数据结构呢？答案是没有（焯！）

但是根据 stackoverflow 上的解释，可以使用 TreeMap<E, Integer> 来模拟 multiset ，其中value是计数器。

关于java中的集合就先说这么多了。

晚安

update 24.5.1

arraylist.toArray(T[] arr)

将Arraylist转化为正宗数组的方法，参数为存数据的数组。未指定默认为 Object[]

例如 arr.toArray(new int[arr.size()][2]); (https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked)

JAVA速成Day2——单例模式

发表于 2024-04-09 更新于 2024-04-15 Disqus：

JAVA速成Day2——单例模式

南软，我的南软

单例模式

确保一个类只有一个实例，并提供该实例的全局访问点。

线程不安全的懒汉式

懒汉代表延迟实例化，即只在需要的时候实例化一个对象。

public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static 
        if(uniqueInstance == null){
            // 这里是线程不安全的
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

线程安全的饿汉式

直接在声明对象的时候创建一个全局静态对象。

public class Singleton {
    private static Singleton uniqueInstance = new Singleton();

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
    }

    public static Singleton getUniqueInstance(){
        return uniqueInstance;
    }
}

这个方式丢失了节约资源的好处。

线程安全的懒汉式

在第一种方式的race condition那里上锁即可。方法是加上 synchronized 关键字。

public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
        System.out.println("love u");
    }

    public static synchronized Singleton getUniqueInstance(){ // 必须要是 static
        if(uniqueInstance == null){
            // 这里是线程安全的
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

但是这里序列化了 getUniqueInstance 方法，失去了多线程并发的意义。

双重校验锁

public class Singleton {
    private volatile static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
        System.out.println("love u");
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static
        if(uniqueInstance == null){
            synchronized (Singleton.class) {
                if(uniqueInstance == null){
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

这里必须使用双重 if ，原因相信你能直接看出来。

至于 volatile 关键字，也是必不可少的。这是因为语句 uniqueInstance = new Singleton(); 并不是原子的，它需要进行：

分配内存空间
初始化对象
将 uniqueInstance 指向对应的内存地址。

但是 jvm 可能会将指令重排，将上述执行顺序更改为1>3>2，这在多线程的情况下是有问题的，可能在另一个线程得到未初始化的对象。

静态内部类

静态内部类。。。这个打codeforces倒是经常用。

public class Singleton {
    private static Singleton uniqueInstance;
    private Singleton(){
        System.out.println("love u, blackbird");
    }

    private static class SingletonHolder{
        private static final Singleton INSTANCE = new Singleton();
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static
        return SingletonHolder.INSTANCE;
    }
}

原理有两点：

静态内部类在 Singleton 外部类加载的时候并没有被加载进内存，只有需要的时候（调用 get 方法）才会加载；
虚拟机提供了线程安全，不会多次加载静态内部类。

很神奇是吧？我也觉得~

枚举实现

这东西我第一次看的时候懵了。代码长这样：

1
2
3

public enum Singleton {
    INSTANCE;
}

挖个坑吧，不是很懂。

枚举

讲真之前我连C语言的enum是干啥的我都不知道。。。

在java中，可以通过 static final 来定义常量：

public class Weekday {
    public static final int SUN = 0;
    public static final int MON = 1;
    public static final int TUE = 2;
    public static final int WED = 3;
    public static final int THU = 4;
    public static final int FRI = 5;
    public static final int SAT = 6;
}

可以通过 Weekday.SUN 等形式来访问这些常量。

当然也可以不用int来定义常量，比如String这种。但是在比较的时候需要把 == 改成 equals()。

当我们的需求不依赖于这种int或者String的类型变量时，可以通过 enum 定义枚举类：

enum Weekday {
    SUN, MON, TUE, WED, THU, FRI, SAT;
}

int day = 1;
if (day == Weekday.SUN) { // Compile error: bad operand types for binary operator '=='
}

Weekday x = Weekday.SUN; // ok!
Weekday y = Color.RED; // Compile error: incompatible types

enum定义的枚举类是一种引用类型，但是可以用 == 来比较。这是因为enum类型的每个常量在jvm中都只有一个实例，你无法new一个enum对象。

if (day == Weekday.FRI) { // ok!
}
if (day.equals(Weekday.SUN)) { // ok, but more code!
}

（或许这也是可以使用enum实现单例模式的原因

enum编译后的结果maybe like：

public final class Color extends Enum { // 继承自Enum，标记为final class
    // 每个实例均为全局唯一:
    public static final Color RED = new Color();
    public static final Color GREEN = new Color();
    public static final Color BLUE = new Color();
    // private构造方法，确保外部无法调用new操作符:
    private Color() {}
}

可以发现，每个枚举对象都对应一个唯一的静态实例。同时构造方法是 private 的，不让你new。

但是，其实可以自定义字段与构造方法：

public class Main {
    public static void main(String[] args) {
        Weekday day = Weekday.SUN;
        if (day.dayValue == 6 || day.dayValue == 0) {
            System.out.println("Work at home!");
        } else {
            System.out.println("Work at office!");
        }
    }
}

enum Weekday {
    MON(1), TUE(2), WED(3), THU(4), FRI(5), SAT(6), SUN(0);

    public final int dayValue; // final!!!

    private Weekday(int dayValue) {
        this.dayValue = dayValue;
    }
}

可以重写 toString() 方法，这样调试输出比较方便：

public class Main {
    public static void main(String[] args) {
        Weekday day = Weekday.SUN;
        if (day.dayValue == 6 || day.dayValue == 0) {
            System.out.println("Today is " + day + ". Work at home!"); // 自动调用day.toString()
        } else {
            System.out.println("Today is " + day + ". Work at office!");
        }
    }
}

enum Weekday {
    MON(1, "星期一"), TUE(2, "星期二"), WED(3, "星期三"), THU(4, "星期四"), FRI(5, "星期五"), SAT(6, "星期六"), SUN(0, "星期日");

    public final int dayValue;
    private final String chinese;

    private Weekday(int dayValue, String chinese) {
        this.dayValue = dayValue;
        this.chinese = chinese;
    }

    @Override
    public String toString() {
        return this.chinese;
    }
}

回过来看单例模式

由于enum类部的对象在整个生命周期只会出现一次，而且无论是哪个enum类引用到的对象是同一个，因此可以据此实现单例模式。

public enum Singleton {
    INSTANCE();
    private String bird;
    private int hh;
    Singleton(){}

    public void setBird(String bird) {
        this.bird = bird;
    }

    public void setHh(int hh) {
        this.hh = hh;
    }

    public int getHh() {
        return hh;
    }

    public String getBird() {
        return bird;
    }


    public static void main(String[] args) {
        Singleton singleton = Singleton.INSTANCE;
        singleton.setBird("blackbird");
        singleton.setHh(2333);
        System.out.println(singleton.getBird() + " " + singleton.getHh());
        Singleton singleton1 = Singleton.INSTANCE;
        System.out.println(singleton1.getBird() + " " + singleton1.getHh());
    }
}
// blackbird 2333
// blackbird 2333

很神奇是吧hh

字符串哈希

发表于 2024-04-03 Disqus：

字符串哈希

将字符串转换为一个哈希值，从而判断两个字符串是否相同。

模板：

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int P = 131;
const int _ = 1510;
ull p[_], h[_];
int n;
char s[_];
void init(){
	p[0] = 1, h[0] = 0;
	for(int i = 1; i <= n; i++){
		p[i] = p[i-1] * P;
		h[i] = h[i-1] * P + s[i];
	}
}

ull get(int l, int r){
	return h[r] - h[l-1] * p[r-l+1];
}

bool substr(int l1, int r1, int l2, int r2){
	return get(l1, r1) == get(l2, r2);
}

上面是P取131或13331，然后模数采用 unsigned long long 的自动溢出机制。

练习题：https://codeforces.com/contest/1943/problem/B。div1的B，难度为2000，中等难度。

这题的重点实际上并不在于字符串哈希，而是在于判 aaa 和 ababa 这种情况。

但是对于整个子串的情况，需要特别判断是否为回文串。

如果你采用上述的哈希方式，你会发现你WA了。原因自然是哈希冲突。

然后我试了很多组 P 和 MOD，最后终于得到了一个不冲突的方案（2333和998244853）：

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int P = 2333;
const int _ = 200010;
const ull mod = 998244853;
ull p[_], h[_], hh[_];
int n, q;
string s;
set<int> even, odd;
void init(){
	p[0] = 1, h[0] = hh[0] = 0; even.clear(); odd.clear();
	for(int i = 1; i <= n; i++){
		p[i] = p[i-1] * P % mod;
		h[i] = h[i-1] * P + s[i-1]; h[i] %= mod;
		hh[i] = hh[i-1] * P + s[n-i]; hh[i] %= mod;
		if(i < n && s[i-1] != s[i]) odd.insert(i);
		if(i < n - 1 && s[i-1] != s[i+1]) even.insert(i);
	}
}

ull geth(int l, int r){
	return (h[r] - h[l-1] * p[r-l+1] % mod + mod) % mod;
}
ull gethh(int l, int r){
	int rr = n - l + 1, ll = n - r + 1;
	return (hh[rr] - hh[ll-1] * p[rr-ll+1] % mod + mod) % mod;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie();
	int T; cin >> T;
	while(T--){
		cin >> n >> q;
		cin >> s;
		init();
		while(q--){
			int l, r;
			cin >> l >> r;
			int len = r - l + 1;
			ll ans = 0;
			if(geth(l, r) != gethh(l, r)) ans = len;
			auto it = odd.lower_bound(l);
			auto it2 = even.lower_bound(l);
			if(it == odd.end() || (*it) >= r){
				;
			}else{
				if(it2 == even.end() || (*it2) >= r - 1)
					ans += 1ll * (len - 1) / 2 * ((len - 1) / 2 + 1);
				else
					ans += 1ll * (len - 1) * len / 2 - 1;
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

事实说明哈希冲突还是很玄学的。因此需要考虑更好的判回文串的方式：Manacher。

有空再写！