【BZOJ4137】【FJOI2015】火星商店问题

Author Avatar
q234rty 3月 04, 2018

线段树套可持久化Trie即可。

如果把一个商品的时间看成横坐标，商店编号看成纵坐标，那么原题可以转化成给定一个坐标平面上的 n 个点，每个点 i 有点权 v_i ， m 次查询，每次给定 x ，查询一个矩形区域内 v_i \oplus x 的最大值。

一个直观的想法是树套树，对 x 轴建线段树，内层使用可持久化Trie支持查询区间 v_i \oplus x 的最大值。注意到可持久化Trie要求按顺序插入，那么我们将所有点按纵坐标排序后再插入线段树。询问时找到这个询问对应的所有横坐标区间，分别查询之后取max即可。

看起来这题已经解决了，然而这个做法的空间复杂度是 O(n \log^2 n) 的，无法通过 256\texttt{MB} 的空间限制。

那怎么办办呢？注意到我们可以离线，我们预先把所有点和询问挂在它们对应的线段树节点上，这样我们只需要对于每个线段树节点建立一次可持久化Trie就可以了。

这样就解决了这题，时间复杂度 O(n \log^2 n) ，空间复杂度 O(n \log n) 。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. int bufpos;
  6. char buf[MAXSIZE];
  7. #define NEG 0
  8. void init(){
  9.     #ifdef LOCAL
  10.         freopen("4137.txt","r",stdin);
  11.     #endif
  12.     buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  13.     bufpos=0;
  14. }
  15. #if NEG
  16. int readint(){
  17.     bool isneg;
  18.     int val=0;
  19.     for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  20.     bufpos+=(isneg=buf[bufpos]=='-');
  21.     for(;isdigit(buf[bufpos]);bufpos++)
  22.         val=val*10+buf[bufpos]-'0';
  23.     return isneg?-val:val;
  24. }
  25. #else
  26. int readint(){
  27.     int val=0;
  28.     for(;!isdigit(buf[bufpos]);bufpos++);
  29.     for(;isdigit(buf[bufpos]);bufpos++)
  30.         val=val*10+buf[bufpos]-'0';
  31.     return val;
  32. }
  33. #endif
  34. char readchar(){
  35.     for(;isspace(buf[bufpos]);bufpos++);
  36.     return buf[bufpos++];
  37. }
  38. int readstr(char* s){
  39.     int cur=0;
  40.     for(;isspace(buf[bufpos]);bufpos++);
  41.     for(;!isspace(buf[bufpos]);bufpos++)
  42.         s[cur++]=buf[bufpos];
  43.     s[cur]='\0';
  44.     return cur;
  45. }
  46. const int maxn=100005;
  47. struct trie{
  48.     struct node{
  49.         int sum,ls,rs;
  50.     }t[maxn*21];
  51.     int cur;
  52.     void clear(){
  53.         cur=ver=0;
  54.     }
  55.     int rt[maxn],ver;
  56.     void insert(int x){
  57.         t[++cur]=t[rt[ver]];
  58.         int o=rt[++ver]=cur;
  59.         for(int i=17;i>=0;i--){
  60.             t[o].sum++;
  61.             int &v=(x>>i&1)?t[o].rs:t[o].ls;
  62.             t[++cur]=t[v];
  63.             o=v=cur;
  64.         }
  65.         t[o].sum++;
  66.     }
  67.     int query(int l,int r,int x){
  68.         // printf("query %d %d %d\n",l,r,x);
  69.         int lo=rt[l-1],ro=rt[r],ans=0;
  70.         for(int i=17;i>=0;i--){
  71.             if (x>>i&1){
  72.                 if (t[t[ro].ls].sum>t[t[lo].ls].sum)
  73.                     lo=t[lo].ls,ro=t[ro].ls,ans|=1<<i;
  74.                 else lo=t[lo].rs,ro=t[ro].rs;
  75.             }else{
  76.                 if (t[t[ro].rs].sum>t[t[lo].rs].sum)
  77.                     lo=t[lo].rs,ro=t[ro].rs,ans|=1<<i;
  78.                 else lo=t[lo].ls,ro=t[ro].ls;
  79.             }
  80.         }
  81.         // puts("after query");
  82.         return ans;
  83.     }
  84. }t;
  85. struct query{
  86.     int l,r,x,ans;
  87. }w[maxn];
  88. struct item{
  89.     int p,v;
  90.     bool operator <(const item& rhs)const{
  91.         return p<rhs.p;
  92.     }
  93. };
  94. int ans[maxn];
  95. struct segtree{
  96.     int n;
  97.     vector<int> q[maxn*4];
  98.     vector<item> a[maxn*4];
  99.     int p;
  100.     item it;
  101.     void update(int o,int l,int r){
  102.         // printf("update %d %d %d\n",o,l,r);
  103.         a[o].push_back(it);
  104.         if (l==r)
  105.             return;
  106.         int mid=(l+r)/2;
  107.         if (p<=mid)
  108.             update(o*2,l,mid);
  109.         else update(o*2+1,mid+1,r);
  110.     }
  111.     int ql,qr,id;
  112.     void addq(int o,int l,int r){
  113.         if (ql<=l && qr>=r){
  114.             q[o].push_back(id);
  115.             return;
  116.         }
  117.         int mid=(l+r)/2;
  118.         if (ql<=mid)
  119.             addq(o*2,l,mid);
  120.         if (qr>mid)
  121.             addq(o*2+1,mid+1,r);
  122.     }
  123.     void work(int o){
  124.         t.clear();
  125.         sort(a[o].begin(),a[o].end());
  126.         for(int i=0;i<a[o].size();i++)
  127.             t.insert(a[o][i].v);
  128.         for(int i=0;i<q[o].size();i++){
  129.             query & qwq=w[q[o][i]];
  130.             int l=lower_bound(a[o].begin(),a[o].end(),(item){qwq.l,0})-a[o].begin()+1,
  131.                 r=upper_bound(a[o].begin(),a[o].end(),(item){qwq.r,0})-a[o].begin();
  132.             if (l>r)
  133.                 continue;
  134.             qwq.ans=max(qwq.ans,t.query(l,r,qwq.x));
  135.         }
  136.     }
  137.     void work(){
  138.         for(int i=1;i<=4*n;i++)
  139.             if (q[i].size() && a[i].size())
  140.                 work(i);
  141.     }
  142. }s;
  143. int main(){
  144.     init();
  145.     int n=readint(),m=readint();
  146.     s.n=m+1;
  147.     for(int i=1;i<=n;i++)
  148.         t.insert(readint());
  149.     // puts("WTF");
  150.     int day=1,cur=0;
  151.     for(int o=1;o<=m;o++){
  152.         int op=readint();
  153.         if (!op){
  154.             int p=readint(),v=readint();
  155.             s.p=++day,s.it=(item){p,v};
  156.             s.update(1,1,s.n);
  157.         }else{
  158.             int l=readint(),r=readint(),x=readint(),d=readint();
  159.             // printf("query %d %d %d %d\n",l,r,x,d);
  160.             w[++cur]=(query){l,r,x,t.query(l,r,x)};
  161.             if (!d)
  162.                 continue;
  163.             s.ql=max(day-d+1,1),s.qr=day,s.id=cur;
  164.             s.addq(1,1,s.n);
  165.         }
  166.     }
  167.     // puts("WTF");
  168.     s.work();
  169.     // printf("cur=%d\n",cur);
  170.     for(int i=1;i<=cur;i++)
  171.         printf("%d\n",w[i].ans);
  172. }

Written with StackEdit.

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/03/04/bzoj4137/

隐藏