danihao123's Blog

好前一段时间因为一些神必原因……博客放到了https://yahyachan.github.io。然后因为我回学校了所以接下来很长时间可能会继续用这个博客？

我谔谔，还是说这题……

对于询问\([l, r]\)，考虑所有数在其中第一次出现的位置，如果说这个数在整个区间里只出现了一次，那么这个数下一次出现的位置一定大于\(r\)。

因此我们用扫描线搞一下就好啦……

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using pii = std::pair<int, int>;
const int maxn = 500005;
const int maxno = maxn << 2;
pii maxv[maxno];
void maintain(int o) {
  maxv[o] = std::max(maxv[o << 1], maxv[o << 1 | 1]);
}
void build_tree(int o, int L, int R) {
  if(L == R) {
    maxv[o] = std::make_pair(-1, -1);
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void modify(int o, int L, int R, const int &p, const pii &v) {
  if(L == R) {
    maxv[o] = v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o);
  }
}
pii query(int o, int L, int R, const int &ql, const int &qr) {
  if(ql <= L && R <= qr) {
    return maxv[o];
  } else {
    int M = (L + R) / 2;
    pii ret = std::make_pair(-100, -100);
    if(ql <= M) ret = std::max(ret, query(o << 1, L, M, ql, qr));
    if(qr > M) ret = std::max(ret, query(o << 1 | 1, M + 1, R, ql, qr));
    return ret;
  }
}

int rec[maxn], next[maxn];
int A[maxn];
std::vector<pii> que[maxn]; int ans[maxn];
int main() {
  int n; scanf("%d", &n);
  std::fill(rec, rec + maxn, n + 1);
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  for(int i = n; i >= 1; i --) {
    next[i] = rec[A[i]];
    rec[A[i]] = i;
  }
  int q; scanf("%d", &q);
  for(int i = 1; i <= q; i ++) {
    int l, r; scanf("%d%d", &l, &r);
    que[l].push_back({r, i});
  }
  build_tree(1, 1, n);
  for(int i = 1; i <= 500000; i ++) {
    if(rec[i] <= n) {
      modify(1, 1, n, rec[i], {next[rec[i]], i});
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(const pii &g : que[i]) {
      int r = g.first, id = g.second;
      pii tmp = query(1, 1, n, i, r);
      if(tmp.first <= r) {
        ans[id] = 0;
      } else {
        ans[id] = tmp.second;
      }
    }
    int nx = next[i];
    if(nx <= n) {
      modify(1, 1, n, nx, {next[nx], A[i]});
    }
  }
  for(int i = 1; i <= q; i ++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

万恶的标题党啊~

这个题明显扫描线辣……但是怎么扫呢？

我们可以考虑对于每个前缀区间[tex][1,r][/tex]先求出他们的[tex]mex[/tex]值，然后用线段树维护。

从[tex][l,r][/tex]转移到[tex][l+1,r][/tex]时，需要将[tex][l,next[l]-1][/tex]（[tex]next[l][/tex]是下一个和[tex]l[/tex]具有相同值的位置）中的所有大于[tex]A[l][/tex]（[tex]l[/tex]的值）的值全部变为[tex]A[l][/tex]。但是这一步怎么做啊……难道要用Segment Beats？

答案是否定的。注意到我们真正需要的只是叶子结点，所以其他非叶子结点的最小值全部弄成无限大，然后这样做就可以把最小值当做标记来弄了……非常精巧。

代码：

/**************************************************************
    Problem: 3339
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1988 ms
    Memory:10396 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=200005,INF=0x7f7f7f7f;
const int maxnode=maxn*4;
int A[maxn];
int minv[maxnode];
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=A[L];
    }else{
        int M=L+(R-L)/2;
        minv[o]=INF;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
    }
}
inline void paint(int o,int v){
    minv[o]=min(minv[o],v);
}
inline void pushdown(int o){
    paint(o<<1,minv[o]);
    paint(o<<1|1,minv[o]);
    minv[o]=INF;
}
int pos;
int query(int o,int L,int R){
    if(L==R)
        return minv[o];
    if(minv[o]<INF)
        pushdown(o);
    int M=L+(R-L)/2;
    if(pos<=M)
        return query(o<<1,L,M);
    else
        return query(o<<1|1,M+1,R);
}
int ql,qr,v;
void update(int o,int L,int R){
    if(ql<=L && R<=qr){
        paint(o,v);
    }else{
        if(minv[o]<INF)
            pushdown(o);
        int M=L+(R-L)/2;
        if(ql<=M)
            update(o<<1,L,M);
        if(qr>M)
            update(o<<1|1,M+1,R);
    }
}
 
inline int readint(){
    register int x=0;
    register char c;
    fread(&c,1,1,stdin);
    while(!isdigit(c))
        fread(&c,1,1,stdin);
    while(isdigit(c)){
        x=x*10+c-'0';
        fread(&c,1,1,stdin);
    }
    return x;
}
int buf[21];
inline void putint(int x){
    register int i,p=0;
    if(!x){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
 
bool vis[maxn];
int last[maxn],next[maxn];
struct Query{
    int id;
    int l,r;
    int ans;
};
bool cmp1(const Query& x,const Query& y){
    if(x.l==y.l)
        return x.r<y.r;
    else
        return x.l<y.l;
}
bool cmp2(const Query& x,const Query& y){
    return x.id<y.id;
}
Query QS[maxn];
int V[maxn];
int main(){
    int n,q;
    register int i,l=1,k=0;
    n=readint();
    q=readint();
    for(i=1;i<=n;i++){
        V[i]=readint();
        vis[V[i]]=true;
        if(k==V[i])
            while(vis[k])
                k++;
        A[i]=k;
    }
    build_tree(1,1,n);
    for(i=n;i>=1;i--){
        if(!last[V[i]])
            next[i]=n+1;
        else
            next[i]=last[V[i]];
        last[V[i]]=i;
    }
    for(i=1;i<=q;i++){
        QS[i].id=i;
        QS[i].l=readint();
        QS[i].r=readint();
    }
    sort(QS+1,QS+1+q,cmp1);
    for(i=1;i<=q;i++){
        while(l<QS[i].l){
            ql=l;
            qr=next[l]-1;
            v=V[l];
            update(1,1,n);
            l++;
        }
        pos=QS[i].r;
        QS[i].ans=query(1,1,n);
    }
    sort(QS+1,QS+1+q,cmp2);
    for(i=1;i<=q;i++){
        putint(QS[i].ans);
    }
    return 0;
}

扫描线处女作TAT

直接离线，按左端点排序扫描。每个点要保存后继相同节点，每种元素第一次出现的位置都加1。然后扫描的时候有后继就给后继加。之后求区间和即可。

代码：

/**************************************************************
    Problem: 1878
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1344 ms
    Memory:8444 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=50001,maxm=200001;
int T[maxn];
int n;
inline int lowbit(int x){
    return x&(-x);
}
inline void update(int p,int v){
    while(p<=n){
        T[p]+=v;
        p+=lowbit(p);
    }
}
inline int query(int p){
    register int ans=0;
    while(p>0){
        ans+=T[p];
        p-=lowbit(p);
    }
    return ans;
}
 
struct Query{
    int l,r;
    int id;
    int ans;
    bool operator <(const Query& x) const{
        return l==x.l?r<x.r:l<x.l;
    }
};
Query Q[maxm];
bool cmp2(const Query& a,const Query& b){
    return a.id<b.id;
}
 
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
 
int next[maxn];
int A[maxn];
int pos[1000001];
int main(){
    int m,maxA=0;
    register int i,j;
    n=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        maxA=max(maxA,A[i]);
    }
    for(i=n;i;i--){
        next[i]=pos[A[i]];
        pos[A[i]]=i;
    }
    for(i=1;i<=maxA;i++)
        if(pos[i])
            update(pos[i],1);
    m=readint();
    for(i=1;i<=m;i++){
        Q[i].l=readint();
        Q[i].r=readint();
        Q[i].id=i;
    }
    sort(Q+1,Q+1+m);
    register int tot=1;
    for(i=1;i<=m;i++){
        while(tot<Q[i].l){
            if(next[tot])
                update(next[tot],1);
            tot++;
        }
        Q[i].ans=query(Q[i].r)-query(Q[i].l-1);
    }
    sort(Q+1,Q+1+m,cmp2);
    for(i=1;i<=m;i++){
        writeint(Q[i].ans);
        putchar('\n');
    }
    return 0;
}