NOIP 2017 提高组 Day2 T3 列队

题目链接: https://loj.ac/problem/2319

Also: https://www.luogu.com.cn/problem/P3960

1 思路

很明显,这个题目需要我们维护 $ n + 1 $ 个序列

这些序列要支持

  • 查询第 $k$ 个
  • 删除第 $k$ 个
  • 在末尾插入

动点脑子的话,树状树组上二分也是可行的,反正我不会

不动脑子的话, Splay 下高问题也不大

2 实现细节

如果把每个节点都单独储存的话,空间 $O(n + m)$ 承受不能

但是考虑到总修改次数很小,而且 Splay 维护的很多节点都是连续的

所以可以让 Splay 把连续的区间当作一个节点

空间问题就解决了

这样时间大概是 $O(q\log m)$ 的…

但是 Splay 的常数巨大…

于是就被 LibreOJ 无情卡常了

大概大力卡还是能过,但是我懒得搞了,反正 Luogu 上过了

3 Code

#include <cstdio>

inline long long seg_len( long long left, long long rig ) { return rig - left + 1; }
template <class T>
T read() {
	T res = 0; char x = getchar();
	while( x < '0' || x > '9' ) {
		x = getchar();
		continue;
	}
	while( x >= '0' && x <= '9' ) {
		res = res * 10 + x - '0';
		x = getchar();
	}
	return res;
}

int st_cnt, st[30];
template <class T>
void write( T res ) {
	while( res ) {
		st_cnt ++;
		st[ st_cnt ] = res % 10;
		res /= 10;
	}
	while( st_cnt ) {
		putchar( st[ st_cnt ] + '0' );
		st_cnt --;
	}
}

const int N = 3e5 + 1e4;

int n, m, q;

struct splay_node {
	splay_node *son[2], *fa;
	long long left, rig, size;
	splay_node( long long _left = 0, long long _rig = 0 ) {
		son[0] = son[1] = fa = 0; size = seg_len( _left, _rig );
		left = _left, rig = _rig;
	}
	void push_up() {
		this -> size = ( this -> son[0]? this -> son[0] -> size: 0 ) 
			+ ( this -> son[1]? this -> son[1] -> size: 0 ) 
			+ seg_len( left, rig );
	}
	bool get_son() { 
		if( this -> fa && this -> fa -> son[1] ) 
			return ( this -> fa -> son[1] ) == this;
		return 0;
	}
	inline long long len() { return seg_len( this -> left, this -> rig ); }
};

struct Splay {
	splay_node *rt;
	void init( long long left, long long rig ) {
		splay_node *c = new splay_node( left, rig );
		rt = c;
		rt -> push_up();
	}
	void rotate( splay_node *cur ) {
		bool kind = cur -> get_son();
		splay_node *tmp_fa = cur -> fa;
		if( tmp_fa == 0 ) 
			return ;
		if( tmp_fa -> fa == 0 ) 
			rt = cur;
		else 
			tmp_fa -> fa -> son[ tmp_fa -> get_son() ] = cur;
		cur -> fa = tmp_fa -> fa;
		tmp_fa -> son[kind] = cur -> son[ kind ^ 1 ];
		if( tmp_fa -> son[kind] )
			tmp_fa -> son[kind] -> fa = tmp_fa;
		cur -> son[ kind ^ 1 ] = tmp_fa; tmp_fa -> fa = cur;
		tmp_fa -> push_up(); cur -> push_up();
	}
	void splay( splay_node *from, splay_node *to = 0 ) {
		while( from -> fa != to ) {
			splay_node *fa = from -> fa;
			if( fa -> fa != to ) 
				rotate( ( fa -> get_son() ) == ( from -> get_son() )? fa: from );
			rotate(from);
		}
	}
	splay_node* find_kth( long long k ) {
		if( k == 0 ) 
			return 0;
		splay_node *cur = rt;
		while( cur ) {
			if( cur -> son[0] ) {
				if( cur -> son[0] -> size < k )
					k -= cur -> son[0] -> size;
				else {
					cur = cur -> son[0];
					continue;
				}
			}
			if( k <= cur -> len() ) 
				break;
			k -= cur -> len();
			if( cur -> son[1] ) {
				cur = cur -> son[1];
				continue;
			}
			return 0;
		}
		return cur;
	}
	splay_node* split_kth( long long k ) {/*{{{*/
		splay_node *cur = find_kth(k); splay(cur);
		if( cur -> son[0] ) 
			k -= cur -> son[0] -> size;
		k = ( cur -> left ) + k - 1;
		splay_node *ori_left = cur -> son[0], *ori_rig = cur -> son[1],
			*left = 0, *rig = 0, *mid;
		mid = new splay_node( k, k );
		if( cur -> left <= k - 1 ) {
			left = new splay_node( cur -> left, k - 1 );
			left -> fa = mid;
		}
		if( k + 1 <= cur -> rig ) {
			rig = new splay_node( k + 1, cur -> rig );
			rig -> fa = mid;
		}

		mid -> son[0] = left; mid -> son[1] = rig;
		splay_node *tmp_left = (left? left: mid), *tmp_rig = (rig? rig: mid);
		tmp_left -> son[0] = ori_left; tmp_rig -> son[1] = ori_rig;
		if( ori_left )
			ori_left -> fa = tmp_left; 
		if( ori_rig )
			ori_rig -> fa = tmp_rig;

		if( left ) 
			left -> push_up();
		if( rig ) 
			rig -> push_up();

		mid -> push_up();
		if( rt == cur ) 
			rt = mid;
		delete( cur );
		return mid;
	}/*}}}*/
	void del_kth( long long k ) {
		splay_node *cur = split_kth(k);
		splay_node *left = find_kth( k - 1 ), *rig = find_kth( k + 1 );
		if( left == 0 || rig == 0 ) {
			splay( cur );
			rt = ( cur -> son[ left == 0 ] ); rt -> fa = 0;
			delete( cur );
			return ;
		}
		splay( left ); splay( rig, left );
		delete( rt -> son[1] -> son[0] );
		rt -> son[1] -> son[0] = 0;
		rt -> son[1] -> push_up(); rt -> push_up();
	}
	void pull_up( splay_node *cur ) {
		if( cur ) {
			cur -> push_up();
			pull_up( cur -> fa );
		}
	}
	splay_node* push_back( long long val ) {
		splay_node *cur = rt;
		while( cur ) {
			if( cur -> son[1] ) {
				cur = cur -> son[1];
				continue;
			}
			cur -> son[1] = new splay_node( val, val );
			cur -> son[1] -> fa = cur;
			cur = cur -> son[1];
			break;
		}
		pull_up( cur );
		splay(cur);
		return cur;
	}
#ifdef debug
	void zxbl( splay_node *cur ) {
		if( cur == 0 ) 
			 return ;
		zxbl( cur -> son[0] );
		for( int i = cur -> left; i <= cur -> rig; i ++ ) 
			printf( "%2lld ", i );
		zxbl( cur -> son[1] );
	}
	void _zxbl() {
		zxbl( this -> rt );
	}
#endif
} T[N];

int main() {
#ifdef woshiluo
	freopen( "luogu.3960.in", "r", stdin );
	freopen( "luogu.3960.out", "w", stdout );
#endif
	n = read<int>(); m = read<int>(); q = read<int>();
	T[0].init( m, m );
	T[1].init( 1, m - 1 );
	for( int i = 2; i <= n; i ++ ){
		T[i].init( 1LL * ( i - 1 ) * m + 1, 1LL * i * m - 1 );
		T[0].push_back( 1LL * i * m );
	}
	while( q -- ) {
		int x, y;
		x = read<int>(); y = read<int>();
		if( y == m ) {
			long long cur = T[0].split_kth(x) -> left;
			write(cur);
			printf( "\n" );
			T[0].push_back(cur); T[0].del_kth(x);
		}
		else {
			Splay &tree = T[x];
			long long cur = tree.split_kth(y) -> left;
			write(cur);
			printf( "\n" );
			tree.push_back( T[0].split_kth(x) -> left ); tree.del_kth(y);
			T[0].push_back(cur); T[0].del_kth(x); 
		}
#ifdef debug
		printf( "%d %d\n", x, y );
		for( int i = 0; i <= n; i ++ ) {
			printf( "T[%d]: ", i );
			T[i]._zxbl();
			printf( "\n" );
		}
#endif
	}
}

初学数据结构:字符串哈希 — Luogu P3370

字符串哈希 在 初学数据结构:哈希表的运用 — POJ 3349 Snowflake Snow Snowflakes 一文中,我们曾提及哈希表的概念。那么,什么是字符串哈希呢? 字符串哈希可以理解为一个P进制的数字,其哈希函数如下

H(i)=( H(i-1)*p+a(i) )%mod
其中i表示从1 – i i-1表示从1 – i-1 a(i) 表示这个字符的值(通常取acill码) p p进制数 mod 取模防止爆炸 仔细一看是个什么???进制转换! 经过这个函数基本上每个字符串都会对应一个整数
是不是有点像 康拓展开? 实际上康拓展开也是一种设计的十分好的哈希
可是我们依然会发现,得出来的值还是有一定几率重的,这个状况就叫做哈希碰撞 一个哈希函数产生碰撞的可能性越低,我们就说这个哈希函数设计的越好 那么如何使自己的字符串哈希函数尽可能的变好呢? 如果mod与p是大质数,那么碰撞可能性会很低Qwq 但是这样依然有可能重复,所以我们一般用两个哈希函数,只有两个值相等时才判等

【模板】字符串哈希

明白了概念就来到模板题目把

题目


题意真的是水到了一个境界,所以我们直接上代码吧qwq

代码


#include <cstdio>
#include <cstring>
using namespace std;
int n;
int p=19260817,mod=1000007,temp,temp2,cnt=0;
int p2=99983,mod2=10000007;
// 双哈希
char a[1600];//读入用
long long hash_tmp[1600],hash_tmp2[1600]// 计算哈希;
bool hash[1100000],hash2[11000000];// 哈希表
long long H(){//第一个哈希函数
    int len=strlen(a+1);
    for(int i=1;i<=len;i++){
        hash_tmp[i]=(hash_tmp[i-1]*p+a[i])%mod;
    }
    return hash_tmp[len];
}
long long H2(){//第二个哈希函数
    int len=strlen(a+1);
    for(int i=1;i<=len;i++){
        hash_tmp2[i]=(hash_tmp2[i-1]*p2+a[i])%mod2;
    }
    return hash_tmp2[len];
}
int main(){// 读入
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",a+1);
        temp=H();
        temp2=H2();
        if((!hash[temp])||(!hash2[temp2])){// 有任意一个没有出现过都表示这个字符串没有出现过
            hash[temp]=true;
            hash2[temp2]=true;
            cnt++;
        }
    }
    printf("%d",cnt);
}

END

]]>

链表入门 – Luogu 1996 约瑟夫问题

链表? 通常而言,我们说链表都是一种动态的数据结构,但是显然对于我这样的蒟蒻以及普通的竞赛考试而言,通过半静态的数组模拟也可以基本上完成对链表的模拟。 日常的日常—简单画图:

a         [ 0 ]            [1]            [2]           [3]
head -> |next|data| -> |next|data| -> |next|data| -> |next|data|
        |  2 | 2  |    |  3 | 4  |    | 1  | 3  |    | 0  |  1 |
如果我们想要遍历这个链表,就是这个顺序:
a[0]->a[2]->a[1]->a[3]-|
相信你已经看出来了next的作用,所以把一个数直接添加进链表的时间复杂度不比数组高哪去了2333 让我们来看看下面这道题:

题面


我们现在有两种操作 ‘ 1 ‘ 与 ‘ 2 ‘ , ‘ 1 ‘ 表示插入,’ 2 ‘表示询问一个数是否添加过 我们先看看这个样例 输入
5
1 3
1 5
2 3
1 4
2 2
输出
Y
N
不用说我们也知道,桶排是可以是解决一切,但是我们如果我们内存不够呢? 这是就要祭出链表了。 我们把要插入的数对大整数进行取模,然后存入p[i]数组及链表当中当中(i表示取模得到的结果) 这样一来我们就对取模解过相同的数建立了链表,接下来只需要递归遍历,这个速度查找,比大多数方法快好多了

约瑟夫问题

题面


题目链接:[https://www.luogu.org/problemnew/show/P1996]
无聊的约瑟夫 很好因为约瑟夫的无聊我们不得不去做这道题。 显然模拟以及数学方法都可以轻松 AC Qwq 不过我肯定还是要讲链表的方法的啦~

代码


可以去除data项
#include <cstdio>
using namespace std;
struct node{
    int next,data;// 不解释
}a[110000];// 假装自己是链表的 a[]
int n,m;
int main(){
// 初始化
    int p,q;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        a[i].data=i;
        a[i].next=i+1;
    }
    p=n;// 从 1 开始报数
    a[n].next=1;// 建立循环队列
    for(int i=1;i<=n;i++){// 每个人都要输出
        for(int j=1;j<=m-1;j++){// 把数传到下一个人
            p=a[p].next;
        }
        q=a[p].next;
        a[p].next=a[q].next;// 去除q节点
        printf("%d ",q);
    }
}
为什么我感觉还是模拟qwq

END

过不了几天, ]]>