線段樹是一種二叉樹結構，能夠在O(logn)時間復雜度之內(nèi)實現(xiàn)對數(shù)組中某一區(qū)間的增刪改查的操作。
關于線段樹的
詳細解釋。
今天我們涉及的是線段樹的單點更新以及區(qū)間查詢功能。
我們以HDU上面的
敵兵布陣為例。
題目描述：
C國的死對頭A國這段時間正在進行軍事演習，所以C國間諜頭子Derek和他手下Tidy又開始忙乎了。A國在海岸線沿直線布置了N個工兵營地,Derek和Tidy的任務就是要監(jiān)視這些工兵營地的活動情況。由于采取了某種先進的監(jiān)測手段，所以每個工兵營地的人數(shù)C國都掌握的一清二楚,每個工兵營地的人數(shù)都有可能發(fā)生變動，可能增加或減少若干人手,但這些都逃不過C國的監(jiān)視。
中央情報局要研究敵人究竟演習什么戰(zhàn)術,所以Tidy要隨時向Derek匯報某一段連續(xù)的工兵營地一共有多少人,例如Derek問:“Tidy,馬上匯報第3個營地到第10個營地共有多少人!”Tidy就要馬上開始計算這一段的總人數(shù)并匯報。但敵兵營地的人數(shù)經(jīng)常變動，而Derek每次詢問的段都不一樣，所以Tidy不得不每次都一個一個營地的去數(shù)，很快就精疲力盡了，Derek對Tidy的計算速度越來越不滿:"你個死肥仔，算得這么慢，我炒你魷魚!”Tidy想：“你自己來算算看，這可真是一項累人的工作!我恨不得你炒我魷魚呢!”無奈之下，Tidy只好打電話向計算機專家Windbreaker求救,Windbreaker說：“死肥仔，叫你平時做多點acm題和看多點算法書，現(xiàn)在嘗到苦果了吧!”Tidy說："我知錯了。。。"但Windbreaker已經(jīng)掛掉電話了。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 閱讀(467) |
評論 (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指令可以使服務器按照指令的設置來執(zhí)行和設置在整個JSP頁面范圍內(nèi)有效的屬性。
HTML標記語言：HTML標記在JSP頁面中作為靜態(tài)的內(nèi)容，瀏覽器將會識別這些HTML標記并執(zhí)行。
嵌入的Java代碼片段：通過向JSP頁面中嵌入Java代碼，可以使頁面生成動態(tài)的內(nèi)容。
JSP表達式：JSP表達式主要用于數(shù)據(jù)的輸出。它可以向頁面輸出內(nèi)容以顯示給用戶，還可以用來動態(tài)地指定HTML標記中屬性的值。
posted @
2015-03-24 14:03 marchalex 閱讀(181) |
評論 (0) |
編輯 收藏功能：通過按鈕打開一個新窗口，并在新窗口的狀態(tài)欄中顯示當前年份。
（1）在主窗口中應用以下代碼添加一個用于打開一個新窗口的按鈕：
<input name="button" value="打開新窗口" type="button" onclick="window.open('newWindow.jsp', '', 'width=400, height=200, status=yes')">
（2）創(chuàng)建一個新的JSP文件，名稱為newWindow.jsp，在該文件中添加以下用于顯示當前年份的代碼：
<script language="javascript">
var mydate = new Date();
var year = "現(xiàn)在是:" + mydate.getFullYear() + "年!";
document.write(year);
</script>
posted @
2015-03-24 13:35 marchalex 閱讀(266) |
評論 (0) |
編輯 收藏1.事件概述
JavaScript與Web頁面之間的交互時通過用戶操作瀏覽器頁面時觸發(fā)相關事件來實現(xiàn)的。例如：
在頁面載入完畢時，將處罰load（載入）事件；
當用戶單擊按鈕時，將觸發(fā)按鈕的click事件等。
用戶響應某個事件而執(zhí)行的處理程序稱為事件處理程序。例如：
當用戶單擊按鈕時，將觸發(fā)按鈕的事件處理程序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，是用戶與頁面上的元素交互時觸發(fā)的。
焦點事件：如blur、DOMFocusIn、DOMFocusOut、focus、focusin、focusout，在元素獲得或失去焦點的時候觸發(fā)，這些事件當中，最為重要的是blur和focus，有一點需要引起注意，這一類事件不會發(fā)生冒泡！
鼠標與滾輪事件：如click、dblclick、mousedown、mouseenter、mouseleave、mousemove、mouseout、mouseover、mouseup，是當用戶通過鼠標在頁面執(zhí)行操作時所觸發(fā)的。
滾輪事件：mousewheel（IE6+均支持）、DOMMouseScroll（FF支持的，與mousewheel效果一樣）。是使用鼠標滾輪時觸發(fā)的。
文本事件：textInput，在文檔中輸入文本觸發(fā)。
鍵盤事件：keydown、keyup、keypress，當用戶通過鍵盤在頁面中執(zhí)行操作時觸發(fā)。
合成事件：DOM3級新增，用于處理IME的輸入序列。所謂IME，指的是輸入法編輯器，可以讓用戶輸入在物理鍵盤上找不到的字符。compositionstart、compositionupdate、compositionend三種事件。
變動事件：DOMsubtreeModified、DOMNodeInserted、DOMNodeRemoved、DOMAttrModified、DOMCharacterDataModified等，當?shù)讓覦OM結構發(fā)生變化時觸發(fā)。IE8-不支持。
變動名稱事件：指的是當元素或者屬性名變動時觸發(fā)，當前已經(jīng)棄用！
對于事件的基本類型，隨著HTML5的出現(xiàn)和發(fā)展，又新增了HTML5事件、設備事件、觸摸事件、手勢事件等各種事件。
posted @
2015-03-24 10:58 marchalex 閱讀(200) |
評論 (0) |
編輯 收藏在JSP中引入JavaScript
1.在頁面中直接嵌入JavaScript
<script language="javascript">...</script>
2.連接外部JavaScript
<script language="javascript" src="sample.js"></script>
變量的聲明用var
var variable;
var variable = value;
寫的函數(shù)
document.write(str);
函數(shù)的定義
function functionName([parameter1, parameter2, ...]) {
statements
[return expression]
}
元素的獲取
document.getElementById(id);
posted @
2015-03-24 09:50 marchalex 閱讀(141) |
評論 (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類實例：實現(xiàn)創(chuàng)建空的Vector對象，并向其添加元素，然后輸出所有元素。
<%@ page import="java.util.*" %>
<%
Vector v = new Vector(); //創(chuàng)建空的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 閱讀(188) |
評論 (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示例：實現(xiàn)創(chuàng)建空的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 閱讀(161) |
評論 (0) |
編輯 收藏
JSP顯示時間的小應用，用于顯示時間并對不同時間顯示不同提示。
如：我在寫這篇博客時打開的效果如下：
| 溫馨提示！ |
| 現(xiàn)在時間為：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">現(xiàn)在時間為：<%= time %></td></tr>
<tr height="70">
<td align="center">
<!-- 以下為嵌入到HTML中的Java代碼，用來生成動態(tài)的內(nèi)容 -->
<%
if(hour >= 24 && hour < 5)
out.print("現(xiàn)在是凌晨！時間還很早，再睡一會兒吧！");
else if(hour >= 5 && hour < 10)
out.print("早上好！新的一天即將開始，您準備好了嗎？");
else if(hour >= 10 && hour < 13)
out.print("午休時間！正午好時光！");
else if(hour >= 13 && hour < 18)
out.print("下午繼續(xù)努力工作吧！");
else if(hour >= 18 && hour < 24)
out.print("已經(jīng)是深夜了，注意休息哦！");
%>
</td>
</tr>
</table>
</center>
</body>
</html>
posted @
2015-03-23 10:19 marchalex 閱讀(219) |
評論 (0) |
編輯 收藏
Crawler類能夠通過寬度優(yōu)先搜索不斷地抓取網(wǎng)站上的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");
}
}
下面是部分輸出內(nèi)容：
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 閱讀(409) |
評論 (0) |
編輯 收藏
今天開始準備寫一個Java可以跑得python編譯器。
基本假設是這樣的：
有一個JFrame，里面有一框，是輸入框也是輸出框，一開始如果有需要輸入的內(nèi)容得先寫到上面去；
然后單擊菜單欄打開python文件；
然后得到的結果就會顯示出來。
目前知識有了一個框架，當test.py內(nèi)容為：
print 123456789+123456789000000000
時，運行程序，現(xiàn)實的效果如下：
代碼如下：
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 閱讀(185) |
評論 (0) |
編輯 收藏