hdu 1166
思路：
点修改+区间求和，数组实现线段树。提交hdu时注意把模板的update改成add（改别的或不改都行，一提交就网页丢失就改这里）。可用树状数组实现。
Code：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define dis(a,b,c,d) sqrt((a-c)*(a-c)+(b-d)*(b-d))
#define ll long long
using namespace std;
ll sum[50005<<2];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void build(int l,int r,int rt) {
if(l==r) {
cin>>sum[rt];
return;
}
int mid=r+l>>1;
build(lson);
build(rson);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
ll query(int a,int b,int l,int r,int rt) {
if(a<=l&&b>=r) return sum[rt];
int mid=r+l>>1;
ll ans=0;
if(a<=mid) ans+=query(a,b,lson);
if(b>mid) ans+=query(a,b,rson);
return ans;
}
void add(int a,ll c,int l,int r,int rt) {
sum[rt]+=c;
if(l==r) return;
int mid=l+r>>1;
if(a<=mid) add(a,c,lson);
else add(a,c,rson);
}
string s;
int t,n,j;
int main() {
js;
cin>>t;
while(t--) {
cout<<"Case "<<++j<<":\n";
int x,y; cin>>n;
build(1,n,1);
while(1) {
cin>>s;
if(s=="End") break;
cin>>x>>y;
if(s=="Query") cout<<query(x,y,1,n,1)<<endl;
else if(s=="Add") add(x,y,1,n,1);
else add(x,-y,1,n,1);
}
}
} hdu 1394
题意：
将此时第一个数移到后面，得到一个新序列，这个序列的逆序数为t，不断重复操作问最小的t是什么。
思路：
这题比较特殊，直接将sum数组全部初始化为0就相当于建树了，线段树主要的任务是求初始序列有多少逆序数，然后通过递推式求出将第一个数移到后面的逆序数，取最小值就行了。
原理：
1.原始序列每一位对总逆序数的贡献等于前面出现比他大的数有多少个，观察到这些数不重复且在0~n-1连续，所以求每一位数的贡献时可以查询区间【a[i]+1,n】的和，然后把a[i]存进去（含有a[i]的区间的值+1）。
2.输入时每个数+1，使序列变为1~n，第一个数移到末尾后，原来的逆序变顺序（数量为a[i]-1），顺序变逆序（数量为n-a[i]），比如第一个数是2，后面比它大的数是n-2个，比它小的是2-1个。所以递推式是now=last+n-2 * a[i]+1。
Code：
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define dis(a,b,c,d) sqrt((a-c)*(a-c)+(b-d)*(b-d))
#define ll long long
using namespace std;
ll sum[5005<<2];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void build(int l,int r,int rt) {
if(l==r) {
cin>>sum[rt];
return;
}
int mid=r+l>>1;
build(lson);
build(rson);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
ll query(int a,int b,int l,int r,int rt) {
if(a<=l&&b>=r) return sum[rt];
int mid=r+l>>1;
ll ans=0;
if(a<=mid) ans+=query(a,b,lson);
if(b>mid) ans+=query(a,b,rson);
return ans;
}
void add(int a,ll c,int l,int r,int rt) {
sum[rt]+=c;
if(l==r) return;
int mid=l+r>>1;
if(a<=mid) add(a,c,lson);
else add(a,c,rson);
}
int n,a[5005];
int main() {
js;
while(cin>>n) {
ll cnt=0;
fill(sum,sum+(n+1<<2),0);
for(int i=1;i<=n;++i) {
cin>>a[i];
++a[i];
cnt+=query(a[i]+1,n,1,n,1);
add(a[i],1,1,n,1);
}
ll ans=cnt;
for(int i=1;i<n;++i) {
cnt+=n-(a[i]<<1)+1;
ans=min(ans,cnt);
}
cout<<ans<<endl;
}
} poj 1195
题意：开头输入0，n表示建立n * n的矩阵，然后输入1 a b c，表示(a，b)处的手机数量增加c，输入2 a b c d，表示以(a，b)为左上角，(c，d)为右下角围起来的矩形区域内的手机数量，输入3表示结束。每行每列的编号0~n-1。
思路：
二维矩阵的单点修改和区间求和，换个思路，就是行区间的单行修改和行区间求和，而某行的修改和行区间的值又是对这一单行的列进行修改或者行区间的列进行求和。（二维线段树）
Code：
#include<cstdio>
#define ll long long
using namespace std;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
int sum[1025<<2][1025<<2],n;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void subupdate(int a,ll val,int l,int r,int rt,int t) {
if(l==r)
sum[t][rt]+=val;
else {
int mid=l+r>>1;
if(a<=mid) subupdate(a,val,lson,t);
else subupdate(a,val,rson,t);
sum[t][rt]=sum[t][rt<<1]+sum[t][rt<<1|1];
}
}
void update(int x,int y,ll val,int l,int r,int rt) {
subupdate(y,val,1,n,1,rt);
if(l!=r) {
int mid=l+r>>1;
if(x<=mid) update(x,y,val,lson);
else update(x,y,val,rson);
}
}
ll subquery(int a,int b,int l,int r,int rt,int t) {
if(a<=l&&b>=r) return sum[t][rt];
int mid=l+r>>1;
ll ans=0;
if(a<=mid) ans+=subquery(a,b,lson,t);
if(b>mid) ans+=subquery(a,b,rson,t);
return ans;
}
ll query(int x,int xx,int y,int yy,int l,int r,int rt) {
if(x<=l&&xx>=r) return subquery(y,yy,1,n,1,rt);
int mid=l+r>>1;
ll ans=0;
if(x<=mid) ans+=query(x,xx,y,yy,lson);
if(xx>mid) ans+=query(x,xx,y,yy,rson);
return ans;
}
int a,b,c,d,op;
int main() {
read(op),read(n);
++n;
while(read(op),1) {
if(op==3) break;
read(a),read(b),read(c);
++a,++b;
if(op==1) update(a,b,c,1,n,1);
else {
read(d);
++c,++d;
printf("%lld\n",query(a,c,b,d,1,n,1));
}
}
return 0;
} poi 2182
简单的单点修改。
不做解释，紫书上有。
代码 戳我传送。
poj 2299
题意：给出一个长度为n的数列，你每一次可以随意交换其中两个数字的位置。问你至少交换几次，才能使得这个数列是个单调递增数列。
思路：
刚开始我把线段树的根搞成了0，区间可以搞成0 ~ n-1，但是根一定不能是0，这道理很简单的，因为0的左孩子还是0。接着是没看到区间不是0 ~ n-1，因为a[i]可能会大于a[i]，然后我以为把区间设为0 ~ 就可以了，wa了一发找题解一看，还要离散化，怎么还要离散化呢，a[i]<=1e9，这么大的数，数组根本开不了这么大，这个憨憨翻译，我还以为是999。
所以只要离散化将a[i]映射到一个大小为n的连续空间里，再计算a[i]前面比a[i]大的数有几个，然后把a[i]的值存到线段树里，全部加起来就是答案了。
Code：
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
template <class T>
inline void read(T &res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
int sum[500000<<2];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void add(int a,int c,int l,int r,int rt) {
sum[rt]+=c;
if(l!=r) {
int mid=l+r>>1;
if(a<=mid) add(a,c,lson);
else add(a,c,rson);
}
}
ll query(int a,int b,int l,int r,int rt) {
if(a<=l&&b>=r) return sum[rt];
int mid=l+r>>1;
ll ans=0;
if(a<=mid) ans+=query(a,b,lson);
if(b>mid) ans+=query(a,b,rson);
return ans;
}
int n,a[500005],b[500005];
int main() {
while(read(n),1) {
if(n==0) break;
ll ans=0;
fill(sum,sum+(n<<2),0);
for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
sort(b+1,b+1+n);
int cnt=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
for(int i=1;i<=n;++i) {
ans+=query(a[i]+1,n,1,n,1);
add(a[i],1,1,n,1);
}
printf("%lld\n",ans);
}
} 
京公网安备 11010502036488号