[TJOI2007]书架题解

文中给了你一些句子，以及让你任意插入某个位置以及查询某个位置的句子。

发现因为是句子很难搞，所以开个 map 离散一下成数字。然后在额外开一个 map 记录这个数字对应的句子。

然后你要写一种支持插入任意位置与查询任意位置的数据结构，显然可以平衡树。

但是我就不写！

使用块状链表的超高速实现，常数小还好写好调。最大的点用时也才 400ms 。代码还短。

// Problem: P3850 [TJOI2007]书架

// Contest: Luogu

// URL: https://www.luogu.com.cn/problem/P3850

// Memory Limit: 125 MB

// Time Limit: 2000 ms

//

// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N = 4e6,siz= 300;

int n,m,sub,bel,tmp[N];

map<string,int>vis;

map<int,string>vib;

vector<int>v[N];

vector<int>::iterator it;

int fin(int &kth){

 for(int i=1;i<=bel;i++){

  kth-=v[i].size();

  if(kth<=0){kth+=v[i].size();return i;}

	}

}

void rebuild(){

 int tot=0;

 for(int i=1;i<=bel;i++){

  for(it=v[i].begin();it!=v[i].end();it++) tmp[++tot]=*it;

   v[i].clear();

 }

 for(int i=1;i<=tot;i++){bel=(i-1)/siz+1;v[bel].push_back(tmp[i]);}

}

void insert(int p,int val){

 int id=fin(p);

	v[id].insert(v[id].begin()+p-1,val);

 if(v[id].size()>10*siz) rebuild();

}

signed main(){

 ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);

 cin>>n;

 for(int i=1;i<=n;i++){

  string s;

  cin>>s;

  vis[s]=++sub;vib[sub]=s;

  bel=(i-1)/siz+1;

  v[bel].push_back(sub);

 }

 cin>>m;

 for(int i=1;i<=m;i++){

  string s;

  int k;

  cin>>s>>k;k++;

  vis[s]=++sub;vib[sub]=s;

  insert(min(k,sub-1),sub);

 }

 int q;

 cin>>q;

 for(int i=1;i<=q;i++){

  int t;

  cin>>t;t++;

  int id=fin(t);

  cout<<vib[v[id][t-1]]<<"\n";

 }

 return 0;

}

巴特西

[TJOI2007]书架题解

最新文章

热门文章

巴特西

[TJOI2007]书架 题解

最新文章

热门文章

[TJOI2007]书架题解