题意:给出”A x”&”B y”两种操作,前者表示查询数列中模ｘ最小的数，如果相等的话，那么输出最近那个数进入数列的顺序
这样的操作容易想到线段树，但会发现建树时不知道怎么具体建树，可以充分利用一下数据范围，对于每个数都建立一个节点，然后直接做就好了，最重要的就是查询时， 对于1~mod-1, mod~2*mod-1, ……这样的一个一个查询，但是容易发现当模数很小的时候，这样会常数很大，不如直接暴力
还有就是要注意不要手写max, min我手写一直TLE但是用了max,min后就900ms好像也不算慢了，还有存在”-1”的情况#include#include #include using namespace std;const int N = 5e5 + 10;#define rep(i, s, t) for(int i = s; i <= t; ++i)#define dec(i, s, t) for(int i = s; i >= t; --i)int n, a[N], id[N], top;struct Bf { int query(int Mod) { int Res = 0, Mo = N; dec(i, top, 1) { if(Mo > (a[i]%Mod)) Res = a[i], Mo = a[i] % Mod; if(!Mo) break; }return Res?id[Res]:-1; }}B;struct Ser { int Min[N<<2]; void update(int h, int pos, int l, int r) { Min[h] = min(Min[h], pos); if(l == r) return ; int Mid = (l+r) >> 1; if(pos <= Mid) update(h<<1, pos, l, Mid); else update(h<<1|1, pos, Mid+1, r); } int query(int h, int ql, int qr, int l, int r) { if((ql <= l && r <= qr) || Min[h]>=N) return Min[h]; int Mid = (l+r) >> 1, Ret = N; if(ql <= Mid) Ret = min(Ret, query(h<<1, ql, qr, l, Mid)); if(Ret < N) return Ret; if(qr > Mid) Ret = min(Ret, query(h<<1|1, ql, qr, Mid+1, r)); return Ret; }}S; void Q(int Mod, int Max) { if(Mod < 4000) printf("%d\n", B.query(Mod)); else { int t, Ret = 0, Mo = N<<1; for(int i = 0; i*Mod <= N; ++i) { int st = max(i*Mod, 1); int ed = min((i+1)*Mod-1, N); t = S.query(1, st, ed, 1, N); if(t >= N) continue; if((t%Mod) < Mo) Mo = t % Mod, Ret = t; else if((t%Mod)== Mo && id[Ret] < id[t]) Ret = t; } printf("%d\n", Ret?id[Ret]:-1); }}int main() {#ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("res.out", "w", stdout);#endif int T = 0, d; char s[3]; while(scanf("%d", &n), n) { int Max = 0; top = 0; if(T) puts(""); printf("Case %d:\n", ++T); rep(i, 0, N-1) id[i] = 0; rep(i, 0, (N<<2)-1) S.Min[i] = N; rep(i, 1, n) { scanf("%s%d", s, &d); if(s[0] == 'A') Q(d, Max); else { Max = max(Max, d); a[++top] = d; id[d] = top; S.update(1, d, 1, N); } } } return 0;}