线段树是一种二叉树结构，能够在O(logn)时间复杂度之内实现对数组中某一区间的增删改查的操作。
关于线段树的
详细解释。
今天我们涉及的是线段树的单点更新以及区间查询功能。
我们以HDU上面的
敌兵布阵为例。
题目描述：
C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.
Java代码：
import java.io.*;
public class Main {
private static final int maxn = 50050;
private static long[] sum = new long[maxn<<2];
private static long[] a = new long[maxn];
private static void pushup(int rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
private static void build(int l, int r, int rt) {
if(l == r) {
sum[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt<<1);
build(mid+1, r, rt<<1|1);
pushup(rt);
}
private static void add(int pos, long value, int l, int r, int rt) {
if(l == r) {
sum[rt] += value;
return;
}
int mid = (l+r) >> 1;
if(pos <= mid) add(pos, value, l, mid , rt<<1);
else add(pos, value, mid+1, r, rt<<1|1);
pushup(rt);
}
private static long query(int L, int R, int l, int r, int rt) {
if(L <= l && r <= R) return sum[rt];
int mid = (l + r) >> 1;
long ans = 0;
if(L <= mid) ans += query(L, R, l, mid, rt<<1);
if(R > mid) ans += query(L, R, mid+1, r, rt<<1|1);
return ans;
}
public static void main(String[] args) throws IOException {
int T, n, cas = 1;
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
T = (int)in.nval;
while(T > 0) {
T --;
out.println("Case " + cas + ":");
cas ++;
in.nextToken();
n = (int)in.nval;
for(int i=1;i<=n;i++) {
in.nextToken();
a[i] = (long)in.nval;
}
build(1, n, 1);
while(true) {
in.nextToken();
String order = (String)in.sval;
if(order.equals("End")) break;
else if(order.equals("Query")) {
in.nextToken();
int L = (int)in.nval;
in.nextToken();
int R = (int)in.nval;
long ans = query(L, R, 1, n, 1);
out.println(ans);
} else if(order.equals("Add")) {
in.nextToken();
int pos = (int)in.nval;
in.nextToken();
long val = (long)in.nval;
add(pos, val, 1, n, 1);
} else if(order.equals("Sub")) {
in.nextToken();
int pos = (int)in.nval;
in.nextToken();
long val = -(long)in.nval;
add(pos, val, 1, n, 1);
}
}
}
out.flush();
}
}
posted @
2015-03-26 08:19 marchalex 阅读(445) |
评论 (0) |
编辑 收藏<!-- JSP中的指令标识 -->
<%@ page language="java" contentType="text/html;charset=gb2312" %>
<%@ page import="java.util.Date" %>
<!-- HTML标记语言 -->
<html>
<head><title>JSP页面的基本构成</title></head>
<body>
<center>
<!-- 嵌入的Java代码 -->
<% String today = new Date().toLocaleString(); %>
<!-- JSP表达式 -->
今天是：<%=today %>
<!-- HTML标记语言 -->
</center>
</body>
</html>
JSP中的指令标识：利用JSP指令可以使服务器按照指令的设置来执行和设置在整个JSP页面范围内有效的属性。
HTML标记语言：HTML标记在JSP页面中作为静态的内容，浏览器将会识别这些HTML标记并执行。
嵌入的Java代码片段：通过向JSP页面中嵌入Java代码，可以使页面生成动态的内容。
JSP表达式：JSP表达式主要用于数据的输出。它可以向页面输出内容以显示给用户，还可以用来动态地指定HTML标记中属性的值。
posted @
2015-03-24 14:03 marchalex 阅读(167) |
评论 (0) |
编辑 收藏功能：通过按钮打开一个新窗口，并在新窗口的状态栏中显示当前年份。
（1）在主窗口中应用以下代码添加一个用于打开一个新窗口的按钮：
<input name="button" value="打开新窗口" type="button" onclick="window.open('newWindow.jsp', '', 'width=400, height=200, status=yes')">
（2）创建一个新的JSP文件，名称为newWindow.jsp，在该文件中添加以下用于显示当前年份的代码：
<script language="javascript">
var mydate = new Date();
var year = "现在是:" + mydate.getFullYear() + "年!";
document.write(year);
</script>
posted @
2015-03-24 13:35 marchalex 阅读(253) |
评论 (0) |
编辑 收藏1.事件概述
JavaScript与Web页面之间的交互时通过用户操作浏览器页面时触发相关事件来实现的。例如：
在页面载入完毕时，将处罚load（载入）事件；
当用户单击按钮时，将触发按钮的click事件等。
用户响应某个事件而执行的处理程序称为事件处理程序。例如：
当用户单击按钮时，将触发按钮的事件处理程序onClick。
事件处理程序的两种分配方式
（1）在JavaScript中分配事件处理程序
例：
<img src="http://gi3.md.alicdn.com/bao/uploaded/i3/TB1tlxaHpXXXXXtaXXXXXXXXXXX_!!0-item_pic.jpg_430x430q90.jpg" id="aimage">
<script language="javascript">
var img = document.getElementById("aimage");
img.onclick = function() {
alert('单击了图片');
}
</script>
在页面中加入上面的代码并运行，则当单击图片aimage时，将弹出“单击了图片”对话框。
在JavaScript中分配时间处理程序时，事件处理程序名称必须小写，才能正确响应事件。
（2）在HTML中分配事件处理程序
例：
<img src="http://gi3.md.alicdn.com/bao/uploaded/i3/TB1tlxaHpXXXXXtaXXXXXXXXXXX_!!0-item_pic.jpg_430x430q90.jpg" onclick="alert('单击了图片');">
2.事件类型
UI事件：如load、unload、error、resize、scroll、select、DOMActive，是用户与页面上的元素交互时触发的。
焦点事件：如blur、DOMFocusIn、DOMFocusOut、focus、focusin、focusout，在元素获得或失去焦点的时候触发，这些事件当中，最为重要的是blur和focus，有一点需要引起注意，这一类事件不会发生冒泡！
鼠标与滚轮事件：如click、dblclick、mousedown、mouseenter、mouseleave、mousemove、mouseout、mouseover、mouseup，是当用户通过鼠标在页面执行操作时所触发的。
滚轮事件：mousewheel（IE6+均支持）、DOMMouseScroll（FF支持的，与mousewheel效果一样）。是使用鼠标滚轮时触发的。
文本事件：textInput，在文档中输入文本触发。
键盘事件：keydown、keyup、keypress，当用户通过键盘在页面中执行操作时触发。
合成事件：DOM3级新增，用于处理IME的输入序列。所谓IME，指的是输入法编辑器，可以让用户输入在物理键盘上找不到的字符。compositionstart、compositionupdate、compositionend三种事件。
变动事件：DOMsubtreeModified、DOMNodeInserted、DOMNodeRemoved、DOMAttrModified、DOMCharacterDataModified等，当底层DOM结构发生变化时触发。IE8-不支持。
变动名称事件：指的是当元素或者属性名变动时触发，当前已经弃用！
对于事件的基本类型，随着HTML5的出现和发展，又新增了HTML5事件、设备事件、触摸事件、手势事件等各种事件。
posted @
2015-03-24 10:58 marchalex 阅读(186) |
评论 (0) |
编辑 收藏在JSP中引入JavaScript
1.在页面中直接嵌入JavaScript
<script language="javascript">...</script>
2.连接外部JavaScript
<script language="javascript" src="sample.js"></script>
变量的声明用var
var variable;
var variable = value;
写的函数
document.write(str);
函数的定义
function functionName([parameter1, parameter2, ...]) {
statements
[return expression]
}
元素的获取
document.getElementById(id);
posted @
2015-03-24 09:50 marchalex 阅读(126) |
评论 (0) |
编辑 收藏Vector类常用方法：
add(int index, Object element);
addElementAt(Object obj, int index);
size();
elementAt(int index);
setElementAt(Object obj, int index);
removeElementAt(int index);
Vector类实例：实现创建空的Vector对象，并向其添加元素，然后输出所有元素。
<%@ page import="java.util.*" %>
<%
Vector v = new Vector(); //创建空的Vector对象
for(int i=0;i<3;i++) {
v.add(new String("福娃" + i));
}
v.remove(1); //移除索引位置为1的元素
//显示全部元素
for(int i=0;i<v.size();i++) {
out.println(v.indexOf(v.elementAt(i))+": "+v.elementAt(i));
}
%>
显示结果为：
0: 福娃0 1: 福娃2
posted @
2015-03-23 11:03 marchalex 阅读(170) |
评论 (0) |
编辑 收藏Java容器之ArrayList类
List集合的实例化：
List<String> l = new ArrayList<String>(); //使用ArrayList类实例化List集合
List<String> l2 = new LinkedList<String>(); //使用LinkedList类实例化List集合
ArrayList常用方法：
add(int index, Object obj);
addAll(int, Collection coll);
remove(int index);
set(int index, Object obj);
get(int index);
indexOf(Object obj);
lastIndexOf(Object obj);
listIterator();
ListIterator(int index);
ArrayList示例：实现创建空的ArrayList对象，并向其添加元素，然后输出所有元素。
<%@ page import="java.util.*" %>
<%
List<String> list = new ArrayList<String>();
for(int i=0;i<3;i++) {
list.add(new String("福娃" + i));
}
list.add(1, "后添加的福娃");
//输出所有元素
Iterator<String> it = list.iterator();
while(it.hasNext()) {
out.println(it.next());
}
%>
输出结果为：
福娃0 后添加的福娃 福娃1 福娃2
LinkedList类的用法与ArrayList类类似。
posted @
2015-03-23 10:57 marchalex 阅读(144) |
评论 (0) |
编辑 收藏
JSP显示时间的小应用，用于显示时间并对不同时间显示不同提示。
如：我在写这篇博客时打开的效果如下：
| 温馨提示！ |
| 现在时间为：2015-03-23 10:17:28 |
| 午休时间！正午好时光！ |
代码：
<%@ page language="java" contentType="text/html; charset=UTF-8"
pageEncoding="UTF-8"%>
<%@ page
import="java.util.Date,java.text.*" %>
<%
Date nowday =
new Date();
//获取当前时间
int hour = nowday.getHours();
//获取日期中的小时
SimpleDateFormat format =
new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
//定义日期格式化对象
String time = format.format(nowday);
//将指定日期格式化为“yyyy-MM-dd HH:mm:ss”形式
%>
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>获取当前时间的JSP程序</title>
</head>
<body>
<center>
<table border="1" width="300">
<tr height="30"><td align="center">温馨提示！</td></tr>
<tr height="80"><td align="center">现在时间为：<%= time %></td></tr>
<tr height="70">
<td align="center">
<!-- 以下为嵌入到HTML中的Java代码，用来生成动态的内容 -->
<%
if(hour >= 24 && hour < 5)
out.print("现在是凌晨！时间还很早，再睡一会儿吧！");
else if(hour >= 5 && hour < 10)
out.print("早上好！新的一天即将开始，您准备好了吗？");
else if(hour >= 10 && hour < 13)
out.print("午休时间！正午好时光！");
else if(hour >= 13 && hour < 18)
out.print("下午继续努力工作吧！");
else if(hour >= 18 && hour < 24)
out.print("已经是深夜了，注意休息哦！");
%>
</td>
</tr>
</table>
</center>
</body>
</html>
posted @
2015-03-23 10:19 marchalex 阅读(202) |
评论 (0) |
编辑 收藏
Crawler类能够通过宽度优先搜索不断地抓取网站上的url。
这里需要用到
FileHelper类的writeFile方法用于写入文件。
代码如下：
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
public class Crawler {
private static HashMap<String, Integer> map =
new HashMap<String, Integer>();
private static int count = 0;
private static int max_count = 200000;
public static String[] getLinks(String content) {
HashMap<String, Integer> map =
new HashMap<String, Integer>();
int len = content.length();
for(
int i=0;i+9 < len;i++) {
if(content.substring(i, i+8).equals("\"http:
//") || content.substring(i, i+9).equals("\"https://")) {
String ss =
new String();
for(
int j=i+1;j<len && content.charAt(j) != '\"';j++) ss += content.charAt(j);
if(map.containsKey(ss))
continue;
map.put(ss,
new Integer(1));
}
}
int N = map.size();
String[] ans =
new String[N];
Iterator<String> iter = map.keySet().iterator();
int cnt = 0;
while (iter.hasNext()) {
String key = iter.next();
ans[cnt++] = key;
}
return ans;
}
private static boolean isPictureUrl(String url) {
int len = url.length();
if(url.substring(len-4, len).equals(".jpg")
|| url.substring(len-4, len).equals(".png")
|| url.substring(len-4, len).equals(".gif"))
return true;
return false;
}
public static void bfs(String u, String filename) {
String ans = "";
Queue<String> queue =
new LinkedList<String>();
map.put(u,
new Integer(1));
count ++;
queue.offer(u);
while ((u = queue.poll()) !=
null) {
System.out.println("digging in " + u);
System.out.println("have digged " + count + " pages now
");
String content;
try {
content = URLAnalysis.getContent(u);
String[] res = getLinks(content);
int n = res.length;
for (
int i = 0; i < n; i++) {
String v = res[i];
if (map.containsKey(v))
continue;
count ++;
ans += v + "\n";
map.put(v,
new Integer(1));
if(
false == isPictureUrl(v))
queue.offer(v);
}
if(count >= max_count)
break;
}
catch (Exception e) {
e.printStackTrace();
}
}
try {
FileHelper.writeFile(ans, filename);
}
catch (Exception e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
bfs("http://www.163.com", "D:\\test321\\urls.txt");
}
}
下面是部分输出内容：
http://
http://focus.news.163.com/15/0319/10/AL2INPO400011SM9.html
http://lady.163.com/15/0317/14/AKTR681900264IJ2.html
http://dajia.163.com/article/147.html#AL1GT1GU0095004J
http://xf.house.163.com/qhd/search/0-0-0-0-0-0-0-0-1.html
http://rd.da.netease.com/redirect?t=mwGQ3t&p=EA7B9E&target=http%3A%2F%2Fwww.kaola.com
http://tech.163.com/15/0321/07/AL7C7U3R000915BF.html
http://yuedu.163.com/book_reader/b39efe40b81843a8ac4eabdd3b756d92_4/cd59ff87a38e48eba21b312c4d26f2c7_4?utm_campaign=163ad&utm_source=163home&utm_medium=tab_1_2_7
http://v.163.com/special/opencourse/financialmarkets.html
http://paopao.163.com/schedule/show?pageId=4050&utm_source=163&utm_medium=wytab01&utm_campaign=warmup
http://xf.house.163.com/zz/search/0-0-0-0-0-0-0-0-1.html
http://sports.163.com/15/0321/10/AL7MA69F00052UUC.html
http://ent.163.com/15/0321/01/AL6NG0GI00031H2L.html
http://img2.cache.netease.com/lady/2014/3/1/201403012352473e66b.jpg
http://love.163.com/?vendor=163.navi.icon&utm_source=163.com&utm_campaign=163navi
http://caipiao.163.com/#from=www
http://money.163.com/15/0321/08/AL7GDD1L00253B0H.html
http://yichuangqingshu.lofter.com/post/21d053_641bd4b?act=qbwysylofer_20150101_01
http://img4.cache.netease.com/tech/2015/3/21/20150321095714dd3c3.jpg
http://m.163.com/iphone/index.html
http://yuanst.blog.163.com/blog/static/186229043201522084612809/
http://lady.163.com/15/0320/00/AL42J3UD00264OCL.html
http://w.163.com/15/0320/15/AL5MBP6J00314C3U.html
http://vhouse.163.com/1421889369882.html
http://img2.cache.netease.com/edu/2015/3/20/2015032017293274fa5.jpg
posted @
2015-03-21 16:59 marchalex 阅读(395) |
评论 (0) |
编辑 收藏
今天开始准备写一个Java可以跑得python编译器。
基本假设是这样的：
有一个JFrame，里面有一框，是输入框也是输出框，一开始如果有需要输入的内容得先写到上面去；
然后单击菜单栏打开python文件；
然后得到的结果就会显示出来。
目前知识有了一个框架，当test.py内容为：
print 123456789+123456789000000000
时，运行程序，现实的效果如下：
代码如下：
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
import javax.swing.JFileChooser;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JList;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JTextArea;
public class CompilerOpener extends JFrame {
private static final int Width = 1000;
private static final int Height = 600;
private static JFrame frame = null;
private static JTextArea textArea = null;
public CompilerOpener() {
frame = new JFrame("Java的python编译器");
textArea = new JTextArea();
textArea.setLineWrap(true);// 激活自动换行功能
frame.add(textArea);
JMenuBar menuBar = new JMenuBar();
frame.setJMenuBar(menuBar);
JMenu fileMenu = new JMenu("文件");
JMenuItem openItem = new JMenuItem("打开");
openItem.addActionListener(new MyAction());
fileMenu.add(openItem);
menuBar.add(fileMenu);
frame.setLocationRelativeTo(null);
frame.setSize(Width, Height);
frame.setLocation(100, 100);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setVisible(true);
}
private class MyAction implements ActionListener {
public void actionPerformed(ActionEvent evt) {
//Object s = evt.getSource();
JFileChooser jfc=new JFileChooser();
jfc.setFileSelectionMode(JFileChooser.FILES_AND_DIRECTORIES );
jfc.showDialog(new JLabel(), "选择");
File file=jfc.getSelectedFile();
int file_len = file.toString().length();
String ans = new String();
if(!file.isFile() || !file.toString().substring(file_len-3, file_len).equals(".py")) {
ans = "请确定你选择的文件是一个正确的python文件!";
} else {
String content = textArea.getText();
ans += content;
ans += "结果：\n";
try {
BufferedReader reader = new BufferedReader(new FileReader(file.toString()));
String line = null;
try {
while((line = reader.readLine()) != null) {
StringTokenizer st = new StringTokenizer(line , " +");
String s , a , b;
s = st.nextToken();
a = st.nextToken();
b = st.nextToken();
char[] ca = a.toCharArray();
char[] cb = b.toCharArray();
int lena = ca.length, lenb = cb.length;
int c = 0,len = lena > lenb ? lena : lenb;
int[] aa = new int[len+1];
for(int i=0;i<len;i++) {
if(lena-1-i >= 0)
c += (ca[lena-1-i] - '0');
if(lenb-1-i >= 0)
c += (cb[lenb-1-i] - '0');
aa[i] = c % 10;
c /= 10;
}
if(c > 0) aa[len++] = 1;
for(int i=len-1;i>=0;i--) ans += aa[i];
ans += "\n";
}
textArea.setText(ans);
} catch (IOException e) {
e.printStackTrace();
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
}
}
public static void main(String[] args) {
new CompilerOpener();
}
}
posted @
2015-03-20 14:19 marchalex 阅读(170) |
评论 (0) |
编辑 收藏