• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

C++ Treap类代码示例

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

本文整理汇总了C++中Treap的典型用法代码示例。如果您正苦于以下问题:C++ Treap类的具体用法?C++ Treap怎么用?C++ Treap使用的例子?那么恭喜您, 这里精选的类代码示例或许可以为您提供帮助。



在下文中一共展示了Treap类的20个代码示例,这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞,您的评价将有助于我们的系统推荐出更棒的C++代码示例。

示例1: forn

 forn(q,Q)
 {
     char op[8];
     scanf("%s", op);
     if (op[0] == 'I')
     {
         int x,y;
         scanf("%d%d", &x,&y);
         x--;
         // Esto es parecido (pero bien diferente :P) al codigo de insertarAUnladoPointer, pero empezando en p en lugar de en root
         // De entrada me comi que era hacer lo mismo exacto que insertarAUnLado, y pegue WA.
         // Y luego me comi otro WA por olvidarme la linea p = p->h(0); :P
         // Moraleja: esto seria bastante mas error prone que el split obvio.
         Nodo<Datos> *p = iesimo(x, t), *nodo = new Nodo<Datos>(y);
         int lado = 0;
         if (p->h(0))
         {
             p = p->h(0);
             lado = 1;
             while (p->h(1)) p = p->h(1);
         }
         p->hang(lado, nodo);
         nodo->flotar();
         t.reroot();
     }
     else if (op[0] == 'D')
     {
         int x;
         scanf("%d", &x);
         x--;
         t.erasePointer(iesimo(x, t));
     }
     else if (op[0] == 'R')
     {
         int x,y;
         scanf("%d%d", &x, &y);
         x--;
         Nodo<Datos> *p = iesimo(x, t);
         p->dat.x = y;
         p->fullUpdate();
     }
     else if (op[0] == 'Q')
     {
         int x,y;
         scanf("%d%d", &x,&y);
         x--;
         assert(x < y);
         Treap<Datos> t2,t3;
          t.splitPointer(iesimo(x, t), t2);
         t2.splitPointer(iesimo(y-x, t2), t3);
         printf("%d\n", t2.root->dat.bestSum);
         t.merge(t2);
         t.merge(t3);
     }
     else
         assert(false);
 }
开发者ID:elsantodel90,项目名称:treap,代码行数:57,代码来源:example3.cpp


示例2: update

    Treap *left_rotate() {
        Treap *y = left;
        left = y->right;
        y->right = this;

        update();
        y->update();

        return y;
    }
开发者ID:riteme,项目名称:test,代码行数:10,代码来源:commit1.cpp


示例3: treap

void treap()
{
    Treap<int> treap;

#define TREAP_LOOP   for (int i = 0; i < 1000; i ++)

	TREAP_LOOP
	{
		treap.Insert(i);
		assert(treap.GetMin() == 0);
		assert(treap.GetMax() == i);
	}

	std::cout<<"Treap constructed"<<std::endl;
	// print keys in sorted order
	treap.InOrderTraversal();

	TREAP_LOOP
	{
		assert(treap.Exists(i));
	}

	TREAP_LOOP
	{
		treap.Delete(i);
	}

	TREAP_LOOP
	{
		assert(!treap.Exists(i));
	}
}
开发者ID:dbremner,项目名称:airhan,代码行数:32,代码来源:main.cpp


示例4: main

int main()
{
    int a[] = {4,1,3,5,2};

    Treap bst = Treap();

    for (int i=0; i<5; i++)
    {
        pair< Treap, Treap > splitedTreap = bst.SplitByVal(a[i]);
        Treap singleNodeTreap = Treap(a[i], 1);

        bst = splitedTreap.X.Join(singleNodeTreap);
        bst = bst.Join(splitedTreap.Y);
    }

    bst.Print();
    return 0;
}
开发者ID:tanmoy13,项目名称:Essential-Codes,代码行数:18,代码来源:Treap.cpp


示例5: main

int main()
{
    Tree<int> tree;
    Treap<int> treap;
    int n = 0;
    cin >> n;
    int value = 0;
    int priority = 0;
    for(int i = 0; i < n; i++) {
        cin >> value >> priority;
        tree.Add(value);
        treap.Add(value, priority);
    }
    
    cout << tree.Height() - treap.Height();
    
    return 0;
}
开发者ID:Lookyan,项目名称:algos,代码行数:18,代码来源:main.cpp


示例6: main

int main()
{
     freopen("Text/ORDERSET.txt","r",stdin);

    int Q; scanf("%d",&Q);

    Treap oTreap;

    while(Q--)
    {
        char t[5];
        int p;
        scanf("%s%d",t,&p);

        if(t[0]=='I')
        {
            oTreap.Insert(p);
        }
        else if(t[0]=='D')
        {
            oTreap.Delete(p);
        }
        else if(t[0]=='K')
        {
            int v = oTreap.FindKth(p);

            if(v > -INF)
            {
                printf("%d\n",v);
            }
            else
                puts("invalid");
        }
        else
        {
            int v = oTreap.Count(p);

            printf("%d\n",v);
        }

    }

    return 0;
}
开发者ID:deepakgupta1313,项目名称:My-Codes,代码行数:44,代码来源:ORDERSET_Spoj.cpp


示例7: TEST

TEST(Treap , Remove)
{
    Treap* tr = new Treap(false);
    size_t n=5000;
    uint32_t* A = (uint32_t*)malloc(n*sizeof(uint32_t));
    for (size_t i=0; i<n; i++) A[i] = rand() % 5001;

    for (size_t i=0; i<n; i++) tr->Insert(A[i]);
    for (size_t i=1; i<n; i+=2) tr->Remove(A[i]);

    for (size_t i=0; i<n; i++) {
        if (i%2==1) {
            CHECK(tr->Find(A[i]) == false);
        }
    }

    free(A);
    delete tr;
}
开发者ID:mpetri,项目名称:OrderedSet,代码行数:19,代码来源:TreapTest.cpp


示例8: main

int main()
{
	try {
		Treap<int> tr;

		tr.push(3);
		tr.push(2);
		tr.push(5);
		tr.push(7);

		tr.print();

		tr.remove(2);

		cout << "\n";
		tr.print();	

		return 0;
	}
        catch(const reaper::error_base &e) {
                cout << e.what() << endl;
                return 1;
        }

}
开发者ID:mikowiec,项目名称:harvest,代码行数:25,代码来源:test_treap.cpp


示例9: main

int main(){
//freopen("My/4554/9.dat", "r", stdin);
Treap * treap = new Treap();
int n, a, b, type;
char c;
scanf("%d", &n);
for( int i=1; i<=n; i++ ){
  scanf("%d %d %d", &type, &a, &b);
  bool res;
  if( type == 1 ){
      scanf(" %c", &c);
      res = treap->insert( a, b - 1, c );
  } else {
      res = treap->erase( a, b - 1 );
  }
  if( res ){
      printf("YES\n");
  } else {
      printf("NO\n");
  }
}
return 0;
}
开发者ID:AlexTsitsura,项目名称:Persistent-Data-Structures,代码行数:23,代码来源:sol.cpp


示例10: solve

void solve(){
    int N,X;
    char ch[5];
    scanf("%d",&N);

    Treap root;
    while(N--){
        scanf("%s%d",ch,&X);
        if (ch[0] == 'I')
            root.Insert_unq(X);//, root.print();
        else if (ch[0] == 'D')
            root.Erase(X);
        else if (ch[0] == 'C'){
            int res = root.Count(X);
            printf("%d\n",res);
        } else {
            int res = root.Kth(X);
            if (res == INT_MIN)
                printf("invalid\n");
            else
                printf("%d\n",res);
        }
    }
}
开发者ID:chang2394,项目名称:Codes,代码行数:24,代码来源:Treap_Split_Merge.cpp


示例11: main

int main()
{
    size_t elementsNumber = 0;
    cin >> elementsNumber;
    if ( elementsNumber == 0 )
    {
        return 1;
    }

    BinaryTree binaryTree;
    Treap treap;
    for ( size_t i = 0; i < elementsNumber; ++i )
    {
        int k = 0;
        int p = 0;
        cin >> k >> p;
        binaryTree.Add( k );
        treap.Add( k, p );
    }

    const int result = (int)treap.GetWidestLayer() - (int)binaryTree.GetWidestLayer();
    cout << result;
    return 0;
}
开发者ID:Applemoon,项目名称:Technopark,代码行数:24,代码来源:main.cpp


示例12: Menu

void Menu()
{
	int val,choice,newVal;
	Treap myTreap;
	while(true)
	{
	do
	{
	cout<<"&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&"<<endl;
	cout<<"       1.插入"<<endl;
	cout<<"       2.删除"<<endl;
	cout<<"       3.修改"<<endl;
	cout<<"       4.查找"<<endl;
	cout<<"       5.显示"<<endl;
	cout<<"       6.返回"<<endl;
	cout<<"请输入你的选项[ ]\b\b";
	cin>>choice; 
	}while(choice!=1&&choice!=2&&choice!=3&&choice!=4&&choice!=5&&choice!=6);
	if(1==choice)
	{
		cin>>val;
		myTreap.InsertTreap(val);
	}
	else if(2==choice)
开发者ID:Busy-York,项目名称:AdvancedDataStructures,代码行数:24,代码来源:Treap.cpp


示例13: main

int main() {
    srand(time(0));
    const int MAX = 1000;

    Treap<int, int> treap;
    for (int i = 0; i < MAX; i++) {
        assert(treap.add(i, i));
    }
    for (int i = 0; i < MAX; i++) {
        assert(treap.contains(i));
    }
    assert(treap.contains(MAX+1) == false);

    assert(treap.remove(7));
    assert(treap.contains(7) == false);

    std::cout << "Finished succesfully." << std::endl;

    return 0;
}
开发者ID:ahluntang,项目名称:tiwi-algoritmen,代码行数:20,代码来源:main.cpp


示例14: main

//test function
int main() {
  Treap treap;

  //printf("test here\n");
  treap.insert(1, 17);
  treap.insert(2, 30);
  treap.insert(3, 47);
  treap.insert(4, 33);
  treap.insert(5, 11);

  treap.print();
  getchar();
  
  treap.del(5);
  treap.print();
  getchar();

  treap.del(1);
  treap.print();
  getchar();

  treap.del(2);
  treap.print();
  //check
}
开发者ID:yuguess,项目名称:ACM,代码行数:26,代码来源:treap.cpp


示例15: main

int main()
{
	/*TreapInit();
	tra.init();

	int i;
	for (int i=0;i<5;i++)
		tra.insert(i);
	tra.inorder(tra.root);
	puts("");

	tra.insert(4);
	tra.inorder(tra.root);
	puts("");

	tra.remove(2);
	tra.inorder(tra.root);
	puts("");

	for (i=1;i<=5;i++)
		printf("the %dth is %d\n",i,tra.find_kth(i));
	for (i=0;i<=5;i++)
		printf("rank of %d is %d\n",i,tra.rank(i));*/

	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	
	
	int t,cas=0;
	char buffer[20];
	int v;

	scanf("%d",&t);
	while (t--)
	{
		cas++;
		printf("Case %d:\n",cas);

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

		assert(1<=n && n<=100000000);
		assert(1<=Q && Q<=100000);

		TreapInit();
		tra.init();
		trb.init();
		M.clear();
		offset=MAX;
		int ans;

		while (Q--)
		{
			scanf("%s%d",buffer,&v);
			assert(1<=v && v<=n);
			switch(buffer[0])
			{
			case 'T':
				top(v);
				break;
			case 'Q':				
				ans=query(v);
				printf("%d\n",ans);
				break;
			case 'R':
				ans=rank(v);
				printf("%d\n",ans);
				break;
			}
		}
	}
	

	return 0;
}
开发者ID:Lin53,项目名称:playground,代码行数:74,代码来源:treap.cpp


示例16: rank

int rank(int v)
{
	int ans;
	if (v<=tra.size()) //at top area
	{
		ans=rm[MAX-1-tra.find_kth(v)];
	}
	else
	{
		if (tra.size()==0)
			ans=v;
		else
		{
			v-=tra.size();
			int lo=1,hi=n,mid;
			while (lo<=hi)
			{
				mid=(lo+hi)/2;
				int tmp=mid-trb.rank(mid);
				if (tmp>=v)
					hi=mid-1;
				else
					lo=mid+1;
			}
			ans=lo;
		}
	}
	return ans;
}
开发者ID:Lin53,项目名称:playground,代码行数:29,代码来源:treap.cpp


示例17: main

int main() {
	int n, low;
	srand(time(0));
	while (EOF != scanf("%d%d", &n, &low)) {
		int k;
		char s[4];
		tr.init();
		while (n--) {
			scanf("%s%d", s, &k);
			if (s[0] == 'I') {
				if (k >= low) {
					tr.insert(k);
				} else {
	//				tr.del_cnt++;
	//				傻逼了,公司都没进,哪来的出公司啊
				}
			} else if (s[0] == 'A') {
				tr.delta += k;
			} else if (s[0] == 'S') {
				tr.delta -= k;
				tr.del_low(low);
			} else if (s[0] == 'F') {
				printf("%d\n", tr.find_kth(tr.size() - k + 1));
			} else {
				for(;;);
			}
		}
		printf("%d\n", tr.del_cnt);
	}
	return 0;
}
开发者ID:leonacwa,项目名称:code,代码行数:31,代码来源:TreapTree[noi2004_cashier].cpp


示例18: top

void top(int v)
{
	if (M.count(v)>0)
		tra.remove(M[v]);
	M[v]=--offset;
	tra.insert(M[v]);
	rm[MAX-1-offset]=v;
	if (!trb.contain(v))
		trb.insert(v);
}
开发者ID:Lin53,项目名称:playground,代码行数:10,代码来源:treap.cpp


示例19: query

int query(int v)
{
	int ans;
	if (M.count(v)>0) // at top area
	{
		ans=tra.rank(M[v]);
	}
	else //add those vi>v at top area
	{
		ans=v+(trb.size()-trb.rank(v));
	}
	return ans;
}
开发者ID:Lin53,项目名称:playground,代码行数:13,代码来源:treap.cpp


示例20: scanf

main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i].x) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i].y) ;
    sort(a+1,a+n+1,cmp) ;
    LL ans=0LL ;
    node *root=NULL ;
    for(int i=1;i<=n;i++) ans+=trp.insert(root,a[i].y) ;
    printf("%lld\n",ans) ;
}
开发者ID:a00012025,项目名称:Online_Judge_Code,代码行数:11,代码来源:a457.cpp



注:本文中的Treap类示例由纯净天空整理自Github/MSDocs等源码及文档管理平台,相关代码片段筛选自各路编程大神贡献的开源项目,源码版权归原作者所有,传播和使用请参考对应项目的License;未经允许,请勿转载。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C++ Tree类代码示例发布时间:2022-05-31
下一篇:
C++ TrayIcon类代码示例发布时间:2022-05-31
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap