[SDOI2019]世界地图

内存限制：512 MB 时间限制：3000 ms

在遥远的艾莉芬特星球上，有着繁荣的艾莉芬特文明。和地球人一样，艾莉芬特人使用经纬度来标记星球上的每个位置。他们把艾莉芬特星球从北到南划分为 $n$ 个纬度，从西到东划分为 $m$ 个经度。在每条经线和纬线相交的地方都有一个国家，他们用 $(i, j)$ 来表示纬度为 $i$，经度为 $j$ 的国家，显然一共有 $n \times m$ 个国家。

艾莉芬特人在任意两个经度或者纬度相邻的国家之间都修建了一条双向道路。

考虑经度相邻的情况：对于任意一个国家 $(i, j)\ (1 \le i \le n, 1 \le j \le m)$，它和国家 $(i, j + 1)$ 之间都有一条道路，特别地当 $j = m$ 时，$(i, m)$ 和 $(i, 1)$ 之间也有一条道路。

考虑纬度相邻的情况：对于任意一个国家 $(i, j)\ (1 \le i < n, 1 \le j \le m)$，它和国家 $(i + 1, j)$ 之间都有一条道路。注意：南北极并不相邻。

艾莉芬特星球并不和平，部分国家卷入了世界大战之中。在接下来 $q$ 个世纪的第 $i$ 个世纪里，经度在 $[l_i, r_i]$ 之间的所有国家都卷入了该世纪发生的世界大战中。当世界大战发生时，被卷入战争的国家都很危险。如果一个国家未被卷入战争，那么它就是一个和平的国家；如果一条道路两端点都是和平的国家，那么它就是一条和平的道路。处于安全考虑，艾莉芬特联合政府会选择只开放一些和平的道路，使得任意两个和平的国家在战争期间都能仅通过这些开放的和平的道路直接或间接连通。

对于任意一条道路，将它保留下来所需的安保代价都不尽相同。请写一个程序，帮助联合政府找到安保代价之和最少的方案。

注意：一个世纪结束后，该世纪的世界大战将会结束，下一场战争的参战国与当前战争的参战国之间没有任何联系。

第一行包含六个正整数 $n, m, \text{SA}, \text{SB}, \text{SC}, \text{lim}$，其中 $n$ 表示纬度的范围，$m$ 表示经度的范围。

为了减少输入量，每条道路的安保代价将由以下代码生成，其中addedge(a,b,c,d,w)表示 $(a, b)$ 和 $(c, d)$ 之间道路的安保代价为 $w$：

unsigned int SA, SB, SC;
int lim;

int getweight() {
    SA^=SA<<16;
    SA^=SA>>5;
    SA^=SA<<1;
    unsigned int t=SA;
    SA=SB;
    SB=SC;
    SC^=t^SA;
    return SC % lim + 1;
}

void gen() {

    scanf("%d%d%u%u%u%d",&n,&m,&SA,&SB,&SC,&lim);
    int i, j, w;

    for(i=1; i<=n; i++)
    for(j=1; j<=m; j++) {
        w=getweight();
        if (j<m) {
            addedge(i, j, i, j+1, w);
        } else {
        addedge(i, j, i,1, w);
        }

    }

    for(i=1; i<n; i++)
    for(j=1; j<=m; j++) {
        w=getweight();
        addedge(i, j, i+1, j, w);
    }
}

第二行包含一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行两个正整数 $l_i, r_i$，依次表示每个询问。

输出 $q$ 行，每行一个整数，依次回答每个询问，即安保代价之和。

样例输入 1

2 4 1 2 3 5
3
2 2
2 3
3 3

样例输出 1

9
5
13

对于$100\%$的数据，$1 < l_i \le r_i < m, 1 \le \text{SA}, \text{SB}, \text{SC} \le 10^9$。

C0707 [SDOI2019]世界地图

题目描述

输入格式

输出

样例

样例输入 1

样例输出 1

提示