kk Blog —— 通用基础

jni 编程

2012-02-15 20:22:00

jni 编译：

g++ -L /usr/lib/jvm/default-java/jre/lib/amd64/server -o judge judge.cpp -ljvm

jni 运行：

以root身份把库路径加入/etc/ld.so.conf或在/etc/ld.so.conf.d中创建特定的.conf文件，然后运行 ldconfig更新/etc/ld.so.cache。例如：在/etc/ld.so.conf.d下创建文件jvm.conf写入

/usr/lib/jvm/default-java/jre/lib/amd64
/usr/lib/jvm/default-java/jre/lib/amd64/server

jni

GetFieldID是得到java类中的参数ID，GetMethodID得到java类中方法的ID，它们只能调用类中声明为 public的参数或方法。使用如下：

jfieldID topicFieldId = env->GetFieldID(objectClass,"name", "Ljava/lang/String;");
jmethodID getcName=env->GetMethodID(objectClass,"getcatName","()Ljava/lang/String;");

第一参数是Java 类对象。第二个参数是参数（或方法名），第三个参数是该参数（或方法）的签名。第三个参数由以下方法得到。有类

public class Cat {
	private int catNumber;
	String catName;
	public Cat(int i,String name){catNumber=i;catName=name;}
	public String getCatName () {
		return this.catName;
	}

	public void setCatName (String catName) {
		this.catName=catName;
	}
}

查看 Cat类进入到Cat所在目录先用javac Cat.java进行编译然后输入命令：

Javap –s Cat

得到Cat方法getcatName 的签名是()Ljava/lang/String，Cat类中的参数是private 所以它没有签名。

options[0].optionString = "-Djava.class.path=./tmp/1";

树套树 -- zju2112 - rujia Liu's Present 3 D

2012-01-16 21:42:00

zju2112

树状数组每个点都是一个SBT

#include <stdio.h>
#include <algorithm>
#include <iostream>

#define N 2000005
using namespace std;

int tol=0;
struct SBT
{
	int left,right;
	int key;
	int size;
	void init()
	{
	    left=right=0;
	    size=1;
	}
}T[N];
void R_Rotate(int &t)//右旋
{
	int k=T[t].left;
	T[t].left=T[k].right;
	T[k].right=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
	return ;
}
void L_Rotate(int &t)//左旋
{
	int k=T[t].right;
	T[t].right=T[k].left;
	T[k].left=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
}
void Maintain(int &t,bool flag)//维护，SBT精华之所在
{
	if(flag==false)
	{
	    if(T[T[T[t].left].left].size>T[T[t].right].size)
	        R_Rotate(t);
	    else if(T[T[T[t].left].right].size>T[T[t].right].size)
	    {
	        L_Rotate(T[t].left);
	        R_Rotate(t);
	    }
	    else
	        return ;
	}
	else
	{
	    if(T[T[T[t].right].right].size>T[T[t].left].size)
	        L_Rotate(t);
	    else if(T[T[T[t].right].left].size>T[T[t].left].size)
	    {
	        R_Rotate(T[t].right);
	        L_Rotate(t);
	    }
	    else
	        return ;
	}
	Maintain(T[t].left,false);
	Maintain(T[t].right,true);
	Maintain(t,false);
	Maintain(t,true);
}
void Insert(int &t,int v)//插入
{
	if(t==0)
	{
	    t=++tol;
	    T[t].init();
	    T[t].key=v;
	}
	else
	{
	    T[t].size++;
	    if(v<T[t].key)
	        Insert(T[t].left,v);
	    else
	        Insert(T[t].right,v);
	    Maintain(t,v>=T[t].key);
	}
}
int Delete(int &t,int v)//删除
{
	if(!t)
	    return 0;
	T[t].size--;
	if(v==T[t].key||v<T[t].key&&!T[t].left||v>T[t].key&&!T[t].right)
	{
	    if(T[t].left&&T[t].right)
	    {
	        int p=Delete(T[t].left,v+1);
	        T[t].key=T[p].key;
	        return p;
	    }
	    else
	    {
	        int p=t;
	        t=T[t].left+T[t].right;
	        return p;
	    }
	}
	else
	    return Delete(v<T[t].key?T[t].left:T[t].right,v);
}
int Find_k(int t,int k)//找出第k大数
{
   if(k<=T[T[t].left].size)
	    return Find_k(T[t].left,k);
	else if(k>T[T[t].left].size+1)
	    return Find_k(T[t].right,k-T[T[t].left].size-1);
	return T[t].key;
}
int Getmin(int t)//取最小值
{
	while(T[t].left)
	    t=T[t].left;
	return t;
}
int Getmax(int t)//取最大值
{
	while(T[t].right)
	    t=T[t].right;
	return t;
}
int Rank(int t,int key)//排名其实就是它的左子树的size+1
{
	if(t==0)
	    return 0;
	if(key<T[t].key)
	    return Rank(T[t].left,key);
	else
	    return T[T[t].left].size+1+Rank(T[t].right,key);
}
int Exist(int t,int x)//判断这个节点是否存在
{
	if(t==0)
	    return 0;
	if(x<T[t].key)
	    return Exist(T[t].left,x);
	else if(x==T[t].key)
	    return 1;
	else
	    return Exist(T[t].right,x);
}
int Count(int t,int x)//统计出现次数
{
	if(!Exist(t,x))
	    return 0;
	else
	    return Rank(t,x+1)-Rank(t,x);
}
int Pred(int t,int v)//返回比v小的最大的数
{
	if(t==0)
	    return v;
	else if(v>T[t].key)
	{
	    int ret=Pred(T[t].right,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Pred(T[t].left,v);
}
int Succ(int t,int v)//返回比v大的最小的数
{
	if(t==0)
	    return v;
	else if(v<T[t].key)
	{
	    int ret=Succ(T[t].left,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Succ(T[t].right,v);
}


int n,m, C[100009], a[100009];

void Myinsert(int x, int y)
{
	while(x <= n) {
	    Insert(C[x], y);
	    x += x&(-x);
	}
}

void Mydelete(int x, int y)
{
	while(x <= n) {
	    Delete(C[x], y);
	    x += x&(-x);
	}
}

int Myrank(int x, int y)
{
	int t=0;
	while(x > 0) {
	    t += Rank(C[x], y);
	    x -= x&(-x);
	}
	return t;
}

int main()
{
	int i,j,k;
	int low,mid,up;
	int T;
	scanf("%d", &T);
	while(T--)
	{
	    scanf("%d %d", &n, &m);
	    tol = 0;
	    for(i=0;i<=n;i++) C[i] = 0;
	    for(i=1;i<=n;i++)
	    {
	        scanf("%d", &a[i]);
	        Myinsert(i, a[i]);
	    }
	    while(m--)
	    {
	        char ch[5];
	        scanf("%s", ch);
	        if(ch[0] == 'Q')
	        {
	            scanf("%d %d %d", &i, &j, &k);
	            low = 0; up = 1000000000;
	            while(low < up)
	            {
	                mid = (low+up)>>1;
	                int s1 = Myrank(i-1, mid);
	                int s2 = Myrank(j, mid);
	                if(s2 - s1 < k)
	                    low = mid+1;
	                else
	                    up = mid;
	            }
	            printf("%d\n", (low+up)>>1);
	        }
	        else
	        {
	            scanf("%d %d", &i, &k);
	            Mydelete(i, a[i]);
	            Myinsert(i, k);
	            a[i] = k;
	        }
	    }
	}
	return 0;
}

SBT -- poj2828

2012-01-16 21:34:00

#include <stdio.h>
#include <algorithm>
#include <iostream>

#define N 4000005
using namespace std;

int tol=0;
struct SBT
{
	int left,right;
	int key;
	int size;
	void init()
	{
	    left=right=0;
	    size=1;
	}
}T[N];

void R_Rotate(int &t)//右旋
{
	int k=T[t].left;
	T[t].left=T[k].right;
	T[k].right=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
	return ;
}
void L_Rotate(int &t)//左旋
{
	int k=T[t].right;
	T[t].right=T[k].left;
	T[k].left=t;
	T[k].size=T[t].size;
	T[t].size=T[T[t].left].size+T[T[t].right].size+1;
	t=k;
}
void Maintain(int &t,bool flag)//维护，SBT精华之所在
{
	if(flag==false)
	{
	    if(T[T[T[t].left].left].size>T[T[t].right].size)
	        R_Rotate(t);
	    else if(T[T[T[t].left].right].size>T[T[t].right].size)
	    {
	        L_Rotate(T[t].left);
	        R_Rotate(t);
	    }
	    else
	        return ;
	}
	else
	{
	    if(T[T[T[t].right].right].size>T[T[t].left].size)
	        L_Rotate(t);
	    else if(T[T[T[t].right].left].size>T[T[t].left].size)
	    {
	        R_Rotate(T[t].right);
	        L_Rotate(t);
	    }
	    else
	        return ;
	}
	Maintain(T[t].left,false);
	Maintain(T[t].right,true);
	Maintain(t,false);
	Maintain(t,true);
}
void Insert(int &t,int v)//插入
{
	if(t==0)
	{
	    t=++tol;
	    T[t].init();
	    T[t].key=v;
	}
	else
	{
	    T[t].size++;
	    if(v<T[t].key)
	        Insert(T[t].left,v);
	    else
	        Insert(T[t].right,v);
	    Maintain(t,v>=T[t].key);
	}
}
int Delete(int &t,int v)//删除
{
	if(!t)
	    return 0;
	T[t].size--;
	if(v==T[t].key||v<T[t].key&&!T[t].left||v>T[t].key&&!T[t].right)
	{
	    if(T[t].left&&T[t].right)
	    {
	        int p=Delete(T[t].left,v+1);
	        T[t].key=T[p].key;
	        return p;
	    }
	    else
	    {
	        int p=t;
	        t=T[t].left+T[t].right;
	        return p;
	    }
	}
	else
	    return Delete(v<T[t].key?T[t].left:T[t].right,v);
}
int Find_k(int t,int k)//找出第k大数
{
   if(k<=T[T[t].left].size)
	    return Find_k(T[t].left,k);
	else if(k>T[T[t].left].size+1)
	    return Find_k(T[t].right,k-T[T[t].left].size-1);
	return T[t].key;
}
int Getmin(int t)//取最小值
{
	while(T[t].left)
	    t=T[t].left;
	return t;
}
int Getmax(int t)//取最大值
{
	while(T[t].right)
	    t=T[t].right;
	return t;
}
int Rank(int t,int key)//排名其实就是它的左子树的size+1
{
	if(t==0)
	    return 0;
	if(key<=T[t].key)
	    return Rank(T[t].left,key);
	else
	    return T[T[t].left].size+1+Rank(T[t].right,key);
}
int eRank(int t,int key)//倒过来排名
{
	if(t==0)
	    return 0;
	if(key>=T[t].key)
	    return eRank(T[t].right,key);
	else
	    return T[T[t].right].size+1+eRank(T[t].left,key);
}

int Exist(int t,int x)//判断这个节点是否存在
{
	if(t==0)
	    return 0;
	if(x<T[t].key)
	    return Exist(T[t].left,x);
	else if(x==T[t].key)
	    return 1;
	else
	    return Exist(T[t].right,x);
}
int Count(int t,int x)//统计出现次数
{
	if(!Exist(t,x))
	    return 0;
	else
	    return Rank(t,x+1)-Rank(t,x);
}
int Pred(int t,int v)//返回比v小的最大的数
{
	if(t==0)
	    return v;
	else if(v>T[t].key)
	{
	    int ret=Pred(T[t].right,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Pred(T[t].left,v);
}
int Succ(int t,int v)//返回比v大的最小的数
{
	if(t==0)
	    return v;
	else if(v<T[t].key)
	{
	    int ret=Succ(T[t].left,v);
	    if(ret==v)
	        return T[t].key;
	    return ret;
	}
	else
	    return Succ(T[t].right,v);
}

////////////////////////

int n,m, a[200009], b[200009], c[200009];

void dfs(int root)
{
	if(root == 0) return;
	dfs(T[root].left);
	if(m > 0) printf(" ");
	printf("%d", T[root].key);
	m++;
	dfs(T[root].right);
}

int main()
{
	int i,j,k;
	int root;
	
	while(scanf("%d", &n) != EOF)
	{
	    tol = 0;
	root = 0;
	    for(i=1;i<=n;i++)
	{
	        scanf("%d %d", &a[i], &b[i]);
	    Insert(root, i);
	}
	for(i=n;i>0;i--)
	{
	    k = Find_k(root, a[i]+1);
	    c[k] = b[i];
	    Delete(root, k);
	}
	for(i=1;i<n;i++) printf("%d ", c[i]);
	printf("%d\n", c[i]);
	m = 0;
	dfs(root);
	}
	return 0;
}

← Older Blog Archives Newer →