从思路上来讲是比较成功的，从分数上就比较令人失望了。
考场上是想到了前两个题的正解思路，其实最后一个题是半个原题，只可惜是我看不懂题。。。
这波呀，这波又是 语文素养限制OI水平。。
改题的时候连官方题解都没看一眼就码过了，感觉不错。
总感觉出题人的题目名字有点。。。（T2的wrxcsd是啥意思？？？？）
T1 牛半仙的妹子图 解题思路做法有很多，比如什么：最小生成树，魔改拓扑排序，等等。
我的做法是 Dij 最短路，看题目第一眼就是某个点到所有点路径上困难值最大值的最小值。
跑一个 Dij 之后直接对于每一个距离离散化一下，进而求出当每种最大的可以克服的困难度可以到达的种类数。
观察到问题是一个区间的值，线段树就算了，毕竟我们不需要修改。
考虑前缀和，查找两个端点在离散化数组里的值，对于整个的部分直接前缀和处理。
对于剩余的部分用剩余部分的区间长度乘上贡献即可。
这种打法对于 \(l=r\) 似乎是不可做的，因此直接特判就行了（逃。
可惜我考场上一时糊涂，把离线和在线分开处理了，然后离线错了，还没特判，\(100pts\rightarrow 55pts\)
本来以为切了的，我裂开。。。
code #include<bits/stdc++.h> #define int long long #define ull unsigned long long #define f() cout<<"Pass"<<endl using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e6+10,M=6e3+10; int n,m,ans,fro,T,opt,mod,dis[N],all[N],qzh[N],pre[N]; int tot,head[N],ver[N<<1],edge[N<<1],nxt[N<<1]; int cnt,lsh[N<<2]; bool vis[N]; priority_queue<pair<int,int> > que; struct Node { int dis,col; }s[N]; struct Ques { int l,r; }q[N]; bool comp(Node x,Node y) { return x.dis<y.dis; } void add_edge(int x,int y,int val) { ver[++tot]=y; edge[tot]=val; nxt[tot]=head[x]; head[x]=tot; } void Dij() { que.push(make_pair(0,fro)); memset(dis,0x3f,sizeof(dis)); dis[fro]=0; while(!que.empty()) { int x=que.top().second; que.pop(); if(vis[x]) continue; vis[x]=true; for(int i=head[x];i;i=nxt[i]) { int to=ver[i],val=edge[i]; if(dis[to]>max(dis[x],val)) { dis[to]=max(dis[x],val); que.push(make_pair(-dis[to],to)); } } } } signed main() { n=read(); m=read(); T=read(); fro=read(); opt=read(); if(opt) mod=read(); for(int i=1;i<=n;i++) s[i].col=read(); for(int i=1,x,y,val;i<=m;i++) { x=read(); y=read(); val=read(); add_edge(x,y,val); add_edge(y,x,val); } for(int i=1;i<=T;i++) { q[i].l=read(); q[i].r=read(); } Dij(); for(int i=1;i<=n;i++) lsh[++cnt]=s[i].dis=dis[i]; sort(lsh+1,lsh+cnt+1); cnt=unique(lsh+1,lsh+cnt+1)-lsh-1; for(int i=1;i<=n;i++) s[i].dis=lower_bound(lsh+1,lsh+cnt+1,s[i].dis)-lsh; sort(s+1,s+n+1,comp); for(int i=1;i<=n;i++) { all[s[i].col]++; int temp=0; if(all[s[i].col]==1) temp=1; qzh[s[i].dis]=qzh[s[i-1].dis]+temp; } for(int i=1;i<=cnt;i++) pre[i]=pre[i-1]+qzh[i-1]*(lsh[i]-lsh[i-1]-1)+qzh[i]; for(int i=1,li,ri;i<=T;i++) { li=q[i].l; ri=q[i].r; if(opt) { li=(li^ans)%mod+1; ri=(ri^ans)%mod+1; if(li>ri) swap(li,ri); } if(li!=ri) { int ls=upper_bound(lsh+1,lsh+cnt+1,li)-lsh; int rs=upper_bound(lsh+1,lsh+cnt+1,ri)-lsh; ans=pre[rs-1]-pre[ls]+qzh[ls]; ans+=(lsh[ls]-li)*qzh[ls-1]+(ri-lsh[rs-1])*qzh[rs-1]; } else { if(li<lsh[cnt]) { int temp=upper_bound(lsh+1,lsh+cnt+1,li)-lsh-1; if(temp<=0) ans=0; else ans=qzh[temp]; } else ans=qzh[cnt]; } printf("%lld\n",ans); } return 0; } T2 牛半仙的妹子Tree 解题思路反正我这个法是个暴力，但是能切题就行。
题库数据是可以直接打过去，但是 yspm 和 zero4338 造了两组数据，成功 Hack 掉了我。。
我又看了一下数据，诶，又是链，我直接来一套 “组合拳”，其实就是对于不同的采用不同的打法。
主要思路这个可以切掉除了Hack数据之外的点，但是优化之前容易被各种链给卡掉（优化思想来自 战神 ）
首先，对于每一个开始不喜欢的点（以后简称为插入）其实需要的只是他插入的时间和位置。
因此我们开一个数组记录下这两个值。
然后在每次查询的时候暴力枚举数组里每一个点与现在查询的点的距离与时间差的关系。
距离可以用 RMQ 或者 树链剖分 来搞，理论上来讲 RMQ 是更快的。
但是实际上，因为 RMQ 初始化时间比较长，所以还是 树链剖分 可能更快一些。
这样的预估分数是 \(40pts\sim 60pts\) 但是出乎意料地搞到了 90pts！！。
优化插入部分，我们发现其实有些节点可以传到的点是可以在别的节点也传到的。
那么我们就没有必要把它给插进去，因此，在每一次插入之前进行一次类似于查询的操作就好了。
特殊判断思路卡掉上面的做法只需要让我们的存储数组里的元素足够多，并且每一次查询都查询最远的两个端点就好了。
因此，WindZR 想出了这样一种做法，适用于所有的类似于链（一个深度十分大的主干上有一些小的分支）
其实就是优化后的扩散。。。
发现每个点有用的扩散只有一次，因此我们记录上一次数组里扩散到的位置。
然后再此基础上接着扩散一个表示每一个是否被扩散到就好了。
清空操作直接清空数组就好了。
其它