bzoj4137 [FJOI2015]火星商店问题

　　比较容易想到的做法是线段树套字典树，修改操作时在字典树上经过的节点维护一个最近被访问过的时间，这样询问操作只经过满足时间条件的节点，时间复杂度O(NlogN^2)但是因为线段树每个节点都要套个字典树，这样的话空间是不够的，不过由于可以离线处理，我们可以先把每个修改和询问操作所访问的线段树节点保存下来，然后一个个节点去做，这样的话空间复杂度就可以保证了。

代码

 #include<cstdio>

 #include<set>

 #include<vector>

 #define N 1000010

 #define M 10000010

 using namespace std;

 int l[N],r[N],n,m,i,a,typ,b,L,R,ti,ans[N],tot,p[N],cnt,flag;

 int s[M][],t[M];

 vector<pair<int,int> > vec[N];

 vector<int> id[N];

 void build(int x,int a,int b)

 {

     int m;

     l[x]=a;r[x]=b;

     if (b-a>)

     {

         m=(a+b)>>;

         build(*x,a,m);

         build(*x+,m,b);

     }

 }

 void insert(int x,int a,int b,pair<int,int> c,int typ)

 {

     int m;

     if (typ==)

     {

         vec[x].push_back(c);

         id[x].push_back(typ);

     }

     if ((a<=l[x])&&(r[x]<=b))

     {

         if (typ)

         {

             vec[x].push_back(c);

             id[x].push_back(typ);

         }

         return;

     }

     m=(l[x]+r[x])>>;

     if (a<m) insert(*x,a,b,c,typ);

     if (m<b) insert(*x+,a,b,c,typ);

 }

 void cl(int x)

 {

     int i;

     for (i=;i<=;i++)

     {

         p[-i+]=x%;

         x=x/;

     }

 }

 void change(int x,int y)

 {

     int now,i;

     cl(x);

     now=;

     for (i=;i<=;i++)

     {

         if (s[now][p[i]]==)

             s[now][p[i]]=++tot;

         now=s[now][p[i]];

         t[now]=max(t[now],y);

     }

 }

 int query(int x,int y)

 {

     int now,i,ans=;

     cl(x);

     now=;

     for (i=;i<=;i++)

     if ((s[now][-p[i]])&&(t[s[now][-p[i]]]>=y))

     {

         now=s[now][-p[i]];

         ans=ans+(<<(-i));

     }

     else

     now=s[now][p[i]];

     return ans;

 }

 void gao(int x)

 {

     int i,a,b;

     for (i=;i<=tot;i++)

     s[i][]=s[i][]=t[i]=;

     tot=;

     for (i=;i<vec[x].size();i++)

     {

         a=vec[x][i].first;

         b=vec[x][i].second;

         if (id[x][i]==)

         change(a,b);

         else

         ans[id[x][i]]=max(ans[id[x][i]],query(a,b));

     }

     if (r[x]-l[x]==)

     return;

     gao(*x);

     gao(*x+);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     build(,,n);

     for (i=;i<=n;i++)

     {

         scanf("%d",&a);

         insert(,i-,i,make_pair(a,m+),);

     }

     ti=;

     for (i=;i<=m;i++)

     {

         scanf("%d",&typ);

         if (typ==)

         {

             scanf("%d%d%d%d",&L,&R,&a,&b);

             insert(,L-,R,make_pair(a,ti-b+),++cnt);

         }

         else

         {

             ti++;

             scanf("%d%d",&a,&b);

             insert(,a-,a,make_pair(b,ti),);

         }

     }

     gao();

     for (i=;i<=cnt;i++)

     printf("%d\n",ans[i]);

 }

巴特西

bzoj4137 [FJOI2015]火星商店问题

最新文章

热门文章