如何建设学校的微网站首页,知名企业网站,视频网站建站程序,微信商城搭建目录知识框架No.1 前缀和NC14556#xff1a;数圈圈NC14600#xff1a;珂朵莉与宇宙NC21195 #xff1a;Kuangyeye and hamburgersNC19798#xff1a;区间权值NC16730#xff1a;runNC15035#xff1a;送分了qaqNo.2 字符串#xff1a;小知识点#xff1a;基于KMP算法的…
目录知识框架No.1 前缀和NC14556数圈圈NC14600珂朵莉与宇宙NC21195 Kuangyeye and hamburgersNC19798区间权值NC16730runNC15035送分了qaqNo.2 字符串小知识点基于KMP算法的字符串匹配AC自动机字符串hash后缀自动机No.3 栈NC15029吐泡泡NC50998括号画家NC15975小c的记事本NC14666最优屏障NC14847Masha与老鼠NC50999表达式计算No.4 最短路径Bellman-Ford算法Dijkstra算法/Dijkstra 优先队列的优化floyd-Warshall算法SPFANC14369最短路很直接NC15522武 很直接NC15549小木乃伊到我家NOI1997最优乘车NC22947香甜的黄油NC17511公交线路NC14292Travel知识框架
No.1 前缀和
NC14556数圈圈
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 1001000
long long n,m,t,k,d;
long long x,y,z;
char ch;
string str;
vectorintv[N];
int num[10]{1,0,0,0,1,0,1,0,2,1}; //0~9
int onum[N1];
int s[N1];
void Init(){for(int i1;iN;i){strto_string(i);for(auto ss:str){int num1ss-0;onum[i]num[num1];}}s[1]0;for(int i2;iN;i){s[i]s[i-1]onum[i];}
}
int main()
{Init();cinn;for(int i0;in;i){cinxy;couts[y]-s[x-1]endl;}return 0;
}NC14600珂朵莉与宇宙
//巧妙地利用求平方 变化为减去平方看差是否存在
//通过指针的指向那么一串数组中的任意子区间就可以用 两个前缀和 进行 相减 得到#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vectorintv[N];
int s[N1];int main()
{cinn;for(int i1;in;i){cinx;s[i]s[i-1]x;}int res0;int cnt[N];cnt[0]1; //前缀和为0的表示 直接前面n个为平方和了//以每一个右边的端点为指针for(int i1;in;i){//找到所有可能的平方和//处理第i个前缀和的所有完全平方数for(int j0;j*js[i];j){cs[i]-j*j; //假设前面有前缀和c的 即if(cnt[c]0){ //如果前面有前缀和c的 代表有子区间为j*jrescnt[c];}}cnt[ s[i] ]; // 已处理过的这个端点加入到cnt里面 表示前面的 前缀和为s[i] 的前缀和的个数加一}coutres;return 0;
}NC21195 Kuangyeye and hamburgers
//vector 的 排序 比如降序 sort(v.rbegin(),v.rend());
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vectorintv[N];
int s[N1]{0};int main()
{cinnm;vectorintans;for(int i1;in;i){cinx;ans.push_back(x);}sort(ans.rbegin(),ans.rend());for(int i0;ians.size();i){s[i1]s[i]ans[i];}int res0;while(m--){cinxy;resmax(res,s[y]-s[x-1]);}coutresendl;return 0;
}NC19798区间权值
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,t,k,d;
long long x,y,z,c;
char ch;
string str;
vectorintv[N];
int s[N1]{0};
int w[N1];
int leijia(int l,int r){return (s[r]-s[l-1])*w[r-l1];
}
int main()
{cinn;for(int i1;in;i){cinx;s[i]s[i-1]x;}for(int i1;in;i){cinw[i];}//下面这个双层循环了导致时间复杂度很高long long res0;for(int i1;in;i){for(int ji;jn;j){resresleijia(i,j);}}//将 j 的那部分再进行前缀和因此要把过程改写for(int j1;jn;j){}coutres%(10000000007);return 0;
}NC16730run
#include bits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
const int N1e55;
long long n,m,t,k,d,q;
long long x,y,z,c;
char ch;
string str;
vectorintv[N];
const int mod1e97;
// 这里的结果如果是 dp[N][3] 就会出错
long long dp[N][2],ans[N];
int main()
{cinqk;dp[0][0]1;for(int i1;iN;i){dp[i][0](dp[i-1][0]dp[i-1][1])%mod; //以走一米的方式走到i米的时候可能情况只能是走i-1米的情况总和if(i-k0){dp[i][1]dp[i-k][0]; // because not can continue two meters runonly one 情况}ans[i](ans[i-1]dp[i][0]dp[i][1])%mod;}for(int i1;iq;i){cinxy;cout(ans[y]-ans[x-1]mod)%modendl;}return 0;
}// 下面是正确的
#include bits/stdc.h
using namespace std;const int N 1e5 5;
const int M 1e9 7;int dp[N][2], s[N];int main() {int q, k, l, r;scanf(%d%d, q, k);dp[0][0] 1;for (int i 1; i N; i) {dp[i][0] (dp[i - 1][0] dp[i - 1][1]) % M;if (i k) {dp[i][1] dp[i - k][0];}s[i] (s[i - 1] dp[i][0] dp[i][1]) % M;}while (q--) {scanf(%d%d, l, r);printf(%d\n, (s[r] - s[l - 1] M) % M);}return 0;
}NC15035送分了qaq
经典基础对x经行分位数处理直到没有位数
#includestdio.h
int check(int x)
{int t0;while(x 0)//对x经行分位数处理直到没有位数{if(x % 10 3){return 1//如果已经有1接下来的位数便不用再判断了直接可以return 1了}x / 10;}return 0;
}
#include stdio.h
int main()
{int m,n;while(scanf(%d%d,n,m)!EOF){if (m 0 n 0)break;int ans0;for(int in;im;i){int xi;while(x){if(x%104||x%10038) {ans;break;}x/10;}}printf(%d\n,ans);}} No.2 字符串
初始模板
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];int main() {return 0;
}小知识点
str.substr(i,n) : 注意不能越界 必须判断以下跳出
基于KMP算法的字符串匹配
暴力搜索 暴力算法自己的想法就是找到第一个相匹配之后就直接转换对象看小字符串去就想那个断痕那个先确定小字符串大小然后for便利到该大小记得加循环跳出时间还有就是字符串可以substr应该会快一点吗 AC自动机
字符串hash
后缀自动机
No.3 栈
NC15029吐泡泡
//全对的
#includeiostream
#includestring
#includestackusing namespace std;int main() // stack 写法
{string str;while(cin str){stackchar st, sk; for(auto ch : str){if(st.size()){auto top st.top();bool flag 1;while(ch top){if(ch o){st.pop();ch O; }else{st.pop();flag 0;break;}if(!st.size()) break;top st.top();}if(flag) st.push(ch);}else{st.push(ch);}}//输出while(st.size()){sk.push(st.top());st.pop();}while(sk.size()){cout sk.top();sk.pop();}puts();}return 0;
}// 对了 百分之四十。
//对于N要进行适应性的更改对于字段错误#includebits/stdc.husing namespace std;#define inf 0x3f3f3f3f#define N 100100int n,m,k,g,d;int x,y,z;char ch;string str;int main() {cinstr;stackcharb;vectorchara;for(auto i:str){a.push_back(i);}for(int i0;ia.size();i){if(b.size()0){char ss;ssb.top();if(ssa[i]sso){b.pop();a[i]O;i--;}else if(ssa[i]ssO){b.pop();}else{b.push(a[i]);}}else{b.push(a[i]);}}vectorcharc;while(!b.empty()){c.push_back(b.top());b.pop();}reverse(c.begin(),c.end());for(auto i:c){couti;}return 0;}NC50998括号画家
例如 (){} 是美观的括号序列而 )({)[}]( 则不是。
思路就是先用i指针 指着开始部位。 再有j指针循环以i起头的可能。//对于N要进行适应性的更改对于字段错误#includebits/stdc.husing namespace std;#define inf 0x3f3f3f3f#define N 100100int n,m,k,g,d;int x,y,z;string str;int main() {cinstr;int res0;//类似双指针了好像for(int i0;istr.size();i){stackcharst;for(int ji;jstr.size();j){if(str[j][){st.push(]);}else if(str[j]{){st.push(});}else if(str[j](){st.push());}else if(st.empty() || str[j]!st.top()){//夭折break;}else{st.pop();//清空代表在此刻是 对称的。if(st.empty())resmax(res,j-i1);}}}coutresendl;return 0;}NC15975小c的记事本
// 自己用 char
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];int main() {ios::sync_with_stdio(false);cinn;stackvectorcharans;vectorcharst;while(n--){cinx;if(x1){ans.push(st);cinstr;for(auto p:str){st.push_back(p);}}else if(x2){ans.push(st);cink;while(k--){st.pop_back();}}else if(x3){cink;coutst[k-1]endl;}else if(x4){stans.top();ans.pop();}}return 0;
}// 别人用 string
#includebits/stdc.h
using namespace std;
int main()
{ios::sync_with_stdio(false);int t;while(cint){stackstrings; //定义一个字符串类型的栈 int a;string s1;s.push();while(t--){cina;if(a1){cins1;s.push(s.top()s1); //向记事本插入字符串 }else if(a2){int k;cink;s1s.top();s.push(s1.substr(0 , s1.length()-k));}else if(a3){int k;cink;s1s.top();couts1[k-1]endl; } else s.pop();}}return 0;
}NC14666最优屏障
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
long long n,m,k,g,d,t;
int x,y,z;
char ch;
string str;
vectorintv[N];
int num(vectorinth , int l, int r){if(lr)return 0;int res0;int maxx0;for(int il;ir;i){maxx0;for(int ji1;jr;j){if(maxxmin(h[i-1],h[j-1]))res;maxxmax(maxx,h[j-1]);}}return res;}
int main() {cint;for(int i1;it;i){cinn;vectorinth;for(int j0;jn;j){cinx;h.push_back(x);}int sumnum(h,1,n);vectorintcnt;cnt.push_back(0);cnt.push_back(0);for(int j2;jn;j){int zuonum(h,1,j-1);int younum(h,j,n);cnt.push_back(sum-zuo-you);}int maxxx0;int weizhi0;for(auto p:cnt)maxxxmax(maxxx,p);for(int j0;jcnt.size();j){if(cnt[j]maxxx){weizhij;break;}}coutCase #i: weizhi maxxxendl;} return 0;
}NC14847Masha与老鼠 NC50999表达式计算
#includebits/stdc.husing namespace std;
char s[50];
stackints1;
stackchars2;int level(char op){if(op||op-)return 1;else if(op*||op/)return 2;else if(op^)return 3;return 0;
}int Pow(int a,int b){int res1;while(b--){res*a;}return res;
}void calc(char op){int x,y;xs1.top();s1.pop();ys1.top();s1.pop();if(op)s1.push(xy);else if(op-)s1.push(y-x);else if(op*)s1.push(x*y);else if(op/)s1.push(y/x);else if(op^)s1.push(Pow(y,x));
}int main(){cins1;int nstrlen(s1),num0;s1.push(0);for(int i1;in;i){if(s[i]0s[i]9){numnum*10s[i]-0;if(s[i1]0||s[i1]9){s1.push(num);num0;}continue;}if(s[i](){s2.push(s[i]);}else{if(s[i])){while(!s2.empty()s2.top()!(){calc(s2.top());s2.pop();}if(!s2.empty()s2.top()()s2.pop();}else{while(!s2.empty()level(s[i])level(s2.top())){calc(s2.top());s2.pop();}s2.push(s[i]);}}}while(!s2.empty()s2.top()!(s2.top()!)){calc(s2.top());s2.pop();}couts1.top()endl;return 0;
}
No.4 最短路径
最短路算法详解_weixin_34018202的博客-CSDN博客
1两种存储方式因为邻接表没有 前向星可观所以 邻接矩阵前向星
NC14501大吉大利晚上吃鸡最短路动态规划
Bellman-Ford算法
Dijkstra算法/Dijkstra 优先队列的优化
NC20131飞行路线
//这个k层免费 不是简单的先找到最短然后去掉k个最大的
floyd-Warshall算法
SPFA
1链式前向星
其中edge[ ] .to表示第i条边的终点, edge[i] .next表示与第i条边同起点的下一条边的存储位置,edge[i] .w为边权值. 另外还有一个数组head[ ],它是用来表示以i为起点的第一条边存储的位置,实际上你会发现这里的第一条边存储的位置其实 在以i为起点的所有边的最后输入的那个编号 head[]数组一般初始化为-1,对于加边的add函数是这样的:
下面是对链式前向星的讲解注意那个 head[u] cnt;//更新以u为起点上一条边的编号 是先赋值再 累加的
链式前向星–最通俗易懂的讲解_sugarbliss的博客-CSDN博客_链式前向星
NC14369最短路很直接
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100100
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];
int mp[20001][200001];
int vis[N];
int dist[N];
int to[N],w[N],head[N]{-1},ne[N],idx0;
//vis数组标记了节点v是否在Q中
void add(int x,int y,int z){to[idx]y;w[idx]z;ne[idx]head[x]; //这条边的上一条边head[x]idx; // 这个点的最后一条边为 idx表示边
}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[1]0;vis[1]1;queueintq;q.push(1);while(q.size()){xq.front();q.pop();vis[x]0;for(int jhead[x];j!-1;jne[j]){//遍历以x为起点的所有的边toint ito[j];if(dist[i]dist[x]w[j]){dist[i]dist[x]w[j];if(vis[i]0){q.push(i);vis[i]1;}}}}
}int main() {memset(head,-1,sizeof(head));cinnm;while(m--){cinxyz;add(x,y,z);}spfa();for(int i2;in;i){coutdist[i]endl;}return 0;
}NC15522武 很直接
//注意 链式前向星的 如果是无向图 需要两次 add 且 数据的N边数要乘以2
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 100010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];
int dist[N],vis[N];
int to[N*2],head[N*2]{-1},ne[N*2],w[N*2];//这个因为是无向图双向
int idx0;
int p;
void add(int x,int y,int z){to[idx]y;w[idx]z;ne[idx]head[x];head[x]idx;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]0;vis[p]1;queueintq;q.push(p);while(q.size()){xq.front();q.pop();vis[x]0;for(int jhead[x];j!-1;jne[j]){int ito[j];if(dist[i]dist[x]w[j]){dist[i]dist[x]w[j];if(vis[i]0){q.push(i);vis[i]1;}}}}
}
int main() {memset(head,-1,sizeof(head));cinnpk;for(int i1;in-1 ;i){cinxyz;add(x,y,z);add(y,x,z);}spfa();sort(dist1,dist1n);coutdist[k1]endl;//离得最短的是本身为0的return 0;
}
NC15549小木乃伊到我家
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];
int dist[N],vis[N];
int to[N*2],head[N*2]{-1},ne[N*2],w[N*2];//这个因为是无向图双向
int idx0;
int p;
void add(int x,int y,int z){to[idx]y;w[idx]z;ne[idx]head[x];head[x]idx;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]0;vis[p]1;queueintq;q.push(p);while(q.size()){xq.front();q.pop();vis[x]0;for(int jhead[x];j!-1;jne[j]){int ito[j];if(dist[i]dist[x]w[j]){dist[i]dist[x]w[j];if(vis[i]0){q.push(i);vis[i]1;}}}}}
int main() {memset(head,-1,sizeof(head));cinnm;p1;//出发点while(m--){cinxyz;add(x,y,z);add(y,x,z);}spfa();if(dist[n]inf)coutqwb bakaendl;else coutdist[n]endl;return 0;
}
NOI1997最优乘车
对于stringstream ss 等的用法
int main(){string s 1 23 # 4;stringstream ss;sss;while(sss){coutsendl;int val convertint(s);coutvalendl;}return 0;
}
输出1 1 23 23 # 0 4 4//第一种方法用bfs 函数类似;//第二种类比距离该条路线距离为0 换乘一次能达到的为距离为1 的点所以最终结果要-1下面用的是这个
// 类比化距离
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];
int dist[N],vis[N],stop[N];
int to[N*2],head[N*2]{-1},ne[N*2],w[N*2];//这个因为是无向图双向
int idx0;
int p;//开始的地方
void add(int x,int y,int z){to[idx]y;w[idx]z;ne[idx]head[x];head[x]idx;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]0;vis[p]1;queueintq;q.push(p);while(q.size()){xq.front();q.pop();vis[x]0;for(int jhead[x];j!-1;jne[j]){int ito[j];if(dist[i]dist[x]w[j]){dist[i]dist[x]w[j];if(vis[i]0){q.push(i);vis[i]1;}}}}}
int main() {memset(head,-1,sizeof(head));cinmn;getchar();while(m--){getline(cin,str);stringstream ssin(str);int cnt0;while(ssinp)stop[cnt]p;for(int i0;icnt;i){for(int ji1;jcnt;j){add(stop[i],stop[j],1);}}}p1;//开始spfa();if(dist[n]inf)coutNOendl;else coutdist[n]-1endl;return 0;
}NC22947香甜的黄油
//问题是图中已经确定的几点到 图中某一点的最短距离
// 即 dist[c1]dist[c2]...dist[cn]//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,c[N],g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];
int dist[N],vis[N],stop[N];
int to[N*2],head[N*2]{-1},ne[N*2],w[N*2];//这个因为是无向图双向
int idx0;
int p;//开始的地方
void add(int x,int y,int z){to[idx]y;w[idx]z;ne[idx]head[x];head[x]idx;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]0;vis[p]1;queueintq;q.push(p);while(q.size()){xq.front();q.pop();vis[x]0;for(int jhead[x];j!-1;jne[j]){int ito[j];if(dist[i]dist[x]w[j]){dist[i]dist[x]w[j];if(vis[i]0){q.push(i);vis[i]1;}}}}}
int main() {memset(head,-1,sizeof(head));int resinf;cindnm;for(int i1;id;i){cinc[i];}while(m--){cinxyz;add(x,y,z);add(y,x,z);}for(int i1;in;i){//以i为起点pi;spfa();int num0;for(int j1;jd;j){numdist[c[j]];}resmin(res,num);}coutresendl;return 0;
}NC17511公交线路
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,c[N],g,s,d;
int x,y,z;
char ch;
string str;
vectorintv[N];
int dist[N],vis[N],stop[N];
int to[N*2],head[N*2]{-1},ne[N*2],w[N*2];//这个因为是无向图双向
int idx0;
int p;//开始的地方
void add(int x,int y,int z){to[idx]y;w[idx]z;ne[idx]head[x];head[x]idx;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]0;vis[p]1;queueintq;q.push(p);while(q.size()){xq.front();q.pop();vis[x]0;for(int jhead[x];j!-1;jne[j]){int ito[j];if(dist[i]dist[x]w[j]){dist[i]dist[x]w[j];if(vis[i]0){q.push(i);vis[i]1;}}}}}
int main() {memset(head,-1,sizeof(head));cinnmsd;ps;while(m--){cinxyz;add(x,y,z);add(y,x,z);}spfa();if(dist[d]inf)cout0endl;else coutdist[d]endl;return 0;
}NC14292Travel
//对于N要进行适应性的更改对于字段错误
#includebits/stdc.h
using namespace std;
#define inf 0x3f3f3f3f
#define N 200010
int n,m,k,q,g,d;
int x,y,z;
char ch;
string str;
vectorintv[N];
int dist[N],vis[N];
int to[N*5],head[N*5]{-1},ne[N*5],w[N*5];//这个因为是无向图双向
int idx0;
int p;
void add(int x,int y,int z){to[idx]y;w[idx]z;ne[idx]head[x];head[x]idx;}
void spfa(){memset(dist,inf,sizeof(dist));memset(vis,0,sizeof(vis));dist[p]0;vis[p]1;queueintq;q.push(p);while(q.size()){xq.front();q.pop();vis[x]0;for(int jhead[x];j!-1;jne[j]){int ito[j];if(dist[i]dist[x]w[j]){dist[i]dist[x]w[j];if(vis[i]0){q.push(i);vis[i]1;}}}}}
int main() {memset(head,-1,sizeof(head));cinnm;for(int i1;in;i){if(in){cinx;add(i,1,x);add(1,i,x);}else{cinx;add(i,i1,x);add(i1,i,x);}}for(int i1;im;i){cinxyz;if(xy)continue;add(x,y,z);add(y,x,z);}cinq;while(q--){cinxy;px;spfa();coutdist[y]endl;}return 0;
}///-------------------------------------------
#includebits/stdc.h
#define ll long long
#define PII pairint,int
using namespace std;
const int N5250110,M22;
ll n,m,q,x,y;
ll p[N],dist[N][M1];
int d[N],h[N],tot,door[M1];
bool st[N];
struct node{int to,nxt,k;
}e[N*2];
void add(int u,int v,int w){e[tot].tov;e[tot].nxth[u];e[tot].kw;h[u]tot;
}
void dijkstra(int x){int sdoor[x];dist[s][x]0;priority_queuePII,vectorPII,greaterPII heap;heap.push({s,0});while(heap.size()){int uheap.top().first;heap.pop();for(int ih[u];i!-1;ie[i].nxt){int ve[i].to;if(dist[v][x]dist[u][x]e[i].k){dist[v][x]dist[u][x]e[i].k;heap.push({v,dist[v][x]});}}}
}
int main(){cinnm;memset(h,-1,sizeof h);memset(dist,0x3f,sizeof dist);for(int i1;in;i) cind[i],p[i]p[i-1]d[i];for(int i1;in;i){add(i,(i1),d[i]);add((i1),i,d[i]);}add(1,n,d[n]),add(n,1,d[n]);int nd0;for(ll i1,u,v,w;im;i){cinuvw;add(u,v,w),add(v,u,w);door[nd]u,door[nd]v;}sort(door1,door1nd);ndunique(door1,door1nd)-(door1);for(int i1;ind;i)dijkstra(i);cinq;while(q--){cinxy;ll lenabs(p[x-1]-p[y-1]);ll ansmin(len,p[n]-len);for(int i1;ind;i)ansmin(ans,dist[x][i]dist[y][i]);coutansendl;}return 0;
}
