原博客食用效果更佳

一.题目

题目描述
牛半仙有 ​个妹子，他把每个妹子都藏到了一座不同的房子中。
这些房子间有条双向道路，每条道路都有一个困难程度​。
牛半仙对每个妹子都赋予了一个类型​。
牛半仙每晚都会多次从自己的家出发，去见所有他能见到的妹子。
牛半仙每次出发见完所有妹子后的都会得到一个愉悦值，为这次见到的妹子的不同种类数个数。
有些道路过于困难，困难程度大于了牛半仙的困难接受程度，牛半仙因为要留尽量多的体力给妹子，所以是不会从这些道路上经过的。
不过牛半仙每出发一次后困难接受程度也会增加。
然而当对困难的接受程度大于最大困难接受程度时，牛半仙这晚就不会再出去了。
牛半仙第i晚的初始困难接受程度​，以及最大困难接受程度，牛半仙想知道他每晚能获得的愉悦值之和。
数据范围
传送门

二.题解

这道题目其实很水，主要难点就是边的权值可以达到，用数组存不下来，但是点只有个，很明显可以离散化，只是这道题会有点麻烦。现在来描述一下过程：

• 用spfa求出到达每个点最小的最大困难值，这里我用的优先队列，但考试的时候直接把优先队列打反了，该从小到大排，结果直接打成从大到小排，居然大样例都过了，最后超时了，我dnm，挂一下优先队列的重载打法。

  friend bool operator < (edge a, edge b){
       return a.mi > b.mi;
  }

• 然后将这些所有的最大困难值离散化，并求出当牛板仙的承受困难程度达到每个最大困难值可以获得的喜悦度，这个好求。
• 然后要来处理一种特殊的前缀和。我们要处理一个当牛板仙的困难承受能力从0达到一个最大困难值时，所能获得的喜悦值之和，这里就涉及离散化的两个最大困难值之间间隔了多少困难值来乘以前一个困难值得喜悦程度就是这个区间内的喜悦度之和。之所以要处理这个东西，是因为要求区间内的喜悦值之和。
• 最后就是求解之间的喜悦值之和。先用求出第一个大于等于的最大困难值，这里要分类来讨论一下：①如果在某两个最大困难值之间，就要加上到的喜悦值之和；②如果在某两个最大困难值之间就要减去到的喜悦值之和。最后加上的喜悦值之和就行了。

  三.Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define M 500005
#define LL long long
const int INF = 1e9 + 5;

struct node {
    int v, w;
    node (){};
    node (int V, int W){
        v = V, w = W;
    }
};
struct edge {
    int v, mi;
    edge (){};
    edge (int V, int MI){v = V, mi = MI;}
    friend bool operator < (edge a, edge b){
        return a.mi > b.mi;
    }
};
struct *** {
    int id, v;
}minn[M];
int n, m, q, h, opt, c[M], mat[M], len;
LL sum[M], ans, pre[M], mod;
bool vis[605];
vector <node> G[M];

void bfs (int s){
    priority_queue <edge> Q;
    Q.push (edge (s, 0));
    for (int i = 1; i <= n; i ++)
        minn[i].v = INF;
    minn[s].v = 0;
    while (! Q.empty ()){
        edge f = Q.top ();
        Q.pop();
        if (f.mi != minn[f.v].v)
            continue;
        for (int i = 0; i < G[f.v].size(); i ++){
            int tmp = G[f.v][i].v, tot = G[f.v][i].w;
            if (minn[tmp].v > max (tot, f.mi)){
                minn[tmp].v = max (tot, f.mi);
                Q.push (edge (tmp, minn[tmp].v));
            }
        }
    }
}
bool cmp (*** a, *** b){
    return a.v < b.v;
}
int main (){
    //freopen ("test.in", "r", stdin);
    //freopen ("test.out", "w", stdout);
    scanf ("%d %d %d %d %d", &n, &m, &q, &h, &opt);
    if (opt)
        scanf ("%lld", &mod);
    for (int i = 1; i <= n; i ++){
        scanf ("%d", &c[i]);
        minn[i].id = i;
    }
    for (int i = 1; i <= m; i ++){
        int u, v, w;
        scanf ("%d %d %d", &u, &v, &w);
        G[u].push_back (node (v, w));
        G[v].push_back (node (u, w));
    }
    bfs (h);
    sort (minn + 1, minn + 1 + n, cmp);
    for (int i = 1; i <= n; i ++)
        mat[i] = minn[i].v;
    len = unique (mat + 1, mat + 1 + n) - mat - 1;
    int id, lst_id = 0;
    for (int i = 1; i <= n; i ++){
        id = lower_bound (mat + 1, mat + 1 + len, minn[i].v) - mat;
        if (! vis[c[minn[i].id]])
            sum[id] = sum[lst_id] + 1ll, vis[c[minn[i].id]] = 1;
        else
            sum[id] = sum[lst_id];
        lst_id = id;
    }
    mat[++ len] = INF;
    for (int i = 1; i <= len; i ++){
        pre[i] = pre[i - 1] + sum[i - 1] * 1ll * (mat[i] - mat[i - 1]);
    }
    while (q --){
        LL l, r;
        scanf ("%lld %lld", &l, &r);
        if (opt){
            l = (l ^ ans) % mod + 1ll;
            r = (r ^ ans) % mod + 1ll;
        }
        if (l > r)
            swap (l, r);
        int lid = lower_bound (mat + 1, mat + 1 + len, l) - mat;
        int rid = lower_bound (mat + 1, mat + 1 + len, r) - mat;
        ans = 0;
        if (mat[lid] > l)
            ans += 1ll * (mat[lid] - l) * sum[lid - 1];
        if (mat[rid] > r){
            if (mat[rid] == INF){
                ans += 1ll * (r - mat[rid - 1] + 1) * sum[rid - 1];
                rid --;
            }
            else
                ans -= 1ll * (mat[rid] - 1 - r) * sum[rid - 1];
        }
        else if (mat[rid] == r){
            ans += sum[rid];
        }
        ans += pre[rid] - pre[lid];
        printf ("%lld\n", ans);
    }
    return 0;
}

Thanks!