#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int tree[1005][1005]={0},n;
int offline()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    return 0;
}
int exit()
{
    fclose(stdin);
    fclose(stdout);
    return 0;
}
int lowbit(int t) 
{  
    return t&(-t); 
} 
int sum(int x,int y) 
{  
    int ans=0;  
    for(int i=x;i>0;i-=lowbit(i))   
        for(int j=y;j>0;j-=lowbit(j))   
            ans+=tree[i][j];
    return ans; 
} 
void plus(int x,int y,int num) 
{  
    for(int i=x;i<=n;i+=lowbit(i))   
        for(int j=y;j<=n;j+=lowbit(j))
            tree[i][j]+=num;
}
int main() 
{
    offline();
    int cnt,t,a,b,x1,x2,y1,y2;
    char order;
    scanf("%d",&cnt);
    while(cnt--)
    {
        memset(tree,0,sizeof(tree));
        scanf("%d %d",&n,&t);
        getchar();
        while(t--)
        {
            scanf("%c",&order);
            if(order=='C')
            {
                scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                getchar();
                plus(x1,y1,1);
                plus(x1,y2+1,1);
                plus(x2+1,y1,1);
                plus(x2+1,y2+1,1);
            }
            else
            {
                scanf("%d %d",&a,&b);
                getchar();
                printf("%d\n",sum(a,b)%2);
            }   
        }
        printf("\n");
    }
    exit();
    return 0;
}

http://wenku.baidu.com/view/d481920527284b73f3425024

AC自动机模板

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 10000000;
struct node
{
    int count;
    int id;
    int deepth;
    node *next[26];
    node *fail;
};
node *q[MAXN];
char keyword[55];
char str[1000010];
int head,tail;
int position[100001];
node *root;
void insert(char *word,node *root,int id)
{
    int index,len;
    node *p = root,*newnode;
    len = strlen(word);
    for(int i=0 ; i < len ; i++ )
    {
        index=word[i]-'a';
        if(!p->next[index])
        {
            newnode=(struct node *)malloc(sizeof(struct node));
            for(int j=0; j<26; j++) newnode->next[j]=0;
            newnode->id=0;
            newnode->count=0;
            newnode->fail=0;
            newnode->deepth=p->deepth+1;
            p->next[index]=newnode;
        }
        p=p->next[index];
    }
    p->count++;
    p->id=id;
}
void build_ac_automation(node *root)
{
    head=0;
    tail=1;
    q[head]=root;
    node *temp,*p;
    while(head<tail)
    {
        temp=q[head++];
        for(int i=0; i< 26 ; i ++)
        {
            if(temp->next[i])
            {
                if(temp==root)temp->next[i]->fail=root;
                else
                {
                    p=temp->fail;
                    while(p)
                    {
                        if(p->next[i])
                        {
                            temp->next[i]->fail=p->next[i];
                            break;
                        }
                        p=p->fail;
                    }
                    if(!p)temp->next[i]->fail=root;
                }
                q[tail++]=temp->next[i];
            }
        }
    }
}
int query(node *root)
{
    int i,cnt=0,index,len=strlen(str);
    node *p=root;
    for(i=0; i < len ; i ++)
    {
        index=str[i]-'a';
        while( !p->next[index] && p != root)p=p->fail;
        p=p->next[index];
        if(!p)p=root;
        node *temp=p;
        while(temp != root )
        {
            if(temp->count>=0)
            {
                cnt+=temp->count;
                position[temp->id]=i+1-temp->deepth;
                temp->count=-1;
            }
            else break;
            temp=temp->fail;
        }
    }
    return cnt;
}
int main()
{
    int i,t,n,ans;
    scanf("%d",&t);
    while(t--)
    {
        memset(position,-1,sizeof(position));
        root=(struct node *)malloc(sizeof(struct node));
        for(int j=0; j<26; j++) root->next[j]=0;
        root->fail=0;
        root->count=0;
        scanf("%d",&n);
        getchar();
        for(i=0; i<n; i++)
        {
            gets(keyword);
            insert(keyword,root,i+1);
        }
        build_ac_automation(root);
        gets(str);
        ans=query(root);
        printf("%d\n",ans);
        //for(int i=1; i<=n; i++)printf("position:%d\n",position[i]);打出匹配位置 
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

二维树状数组模板

#include<cstdio>
#include<cstdlib>
#include<cstring>
int num[10001][10001]={0},tree[10001][10001]={0};
int n,x,y;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x,int y)
{
       int sum = 0;
    for(int i=x;i>0;i-=lowbit(i))
         for(int j=y;j>0;j-=lowbit(j))
             sum += tree[i][j];
      return sum;
}
void plus(int x,int y,int num)
{
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
              tree[i][j] += num;
}
int main()
{
    scanf("%d",&n);
    scanf("%d %d",&x,&y);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&num[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            plus(i,j,num[i][j]);
    printf("%d\n",sum(x,y));
    return 0;
}

一维树状数组模板

#include<cstdio>
#include<cstdlib>
#include<cstring>
int num[100002]={0},tree[100002]={0};
int n,l,r;
int lowbit(int x)
{
    return x&(-x);
}
int sum(int pos)
{
       int sum=0;
       while(pos>0)
       {
         sum+=tree[pos];
         pos-=lowbit(pos);
      }
      return sum;
}
void plus(int pos, int num)
{
       while(pos<=n)
    {
         tree[pos]+=num;
         pos+=lowbit(pos);
      }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&num[i]);
    for(int i=1;i<=n;i++)plus(i,num[i]);
    printf("%d\n",sum(n));
    return 0;
}

KMP算法模板

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
char s[100001],t[100001];
int next[100001];
int getnext(char* t,int *next)
{
    next[0]=-1;
    next[1]=0;
    int len=strlen(t);
    int i=1,j=0;
    while(i<len && j<len)
    {
        if(j==-1 || t[i]==t[j])next[++i]=++j;
        else j=next[j];
    }
    return 0;
}
int kmp(char *s,char *t)
{
    int i=0,j=0,len1=strlen(s),len2=strlen(t);
    while(i<len1 && j<len2)
    {
        if(j==-1 || s[i]==t[j])
        {
            i++;
            j++;
        }
        else j=next[j];
        if(j==len2)return i-len2;
    }
    return -1;
}
int main()
{
    freopen("kmp.in","r",stdin);
    freopen("kmp.out","w",stdout);
    scanf("%s",s);
    getchar();
    scanf("%s",t);
    getnext(t,next);
    printf("%d\n",kmp(s,t));
    fclose(stdin);
    fclose(stdout);
    return 0;
}

计算几何模板系列

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
const double PI=3.14159265358979;
const double EPS=1e-10;
using namespace std;

inline double min(double a,double b)
{
    return a<b?a:b;
}

inline double max(double a,double b)
{
    return a>b?a:b;
}

int dcmp(double x)
{
    if(fabs(x)<=EPS)return 0;
    return x<0?-1:1;
}

class vector//向量 
{
    public:
        double x,y;
        //构造函数 
        vector():x(0.0),y(0.0){}
        vector(double px,double py):x(px),y(py){}
        vector(double x1,double y1,double x2,double y2):x(x2-x1),y(y2-y1){}
        //向量运算 
        vector operator+(const vector& p)
        {
            return vector(x+p.x,y+p.y);
        }
        vector operator-(const vector& p)
        {
            return vector(x-p.x,y-p.y);
        }
        vector operator-()
        {
            return vector(-x,-y);
        }
        double operator*(const vector& p)//点积 
        {
            return x*p.x+y*p.y;
        }
        vector operator*(const double p)//数量积 
        {
            return vector(x*p,y*p);
        }
        double operator^(const vector& p)//叉积 
        {
            return x*p.y-y*p.x;
        }
        vector& operator+=(const vector& p)
        {
            x+=p.x;
            y+=p.y;
            return *this;
        }
        vector& operator-=(const vector& p)
        {
            x-=p.x;
            y-=p.y;
            return *this;
        }
        vector& operator*=(const double p)//数量积 
        {
            x*=p;
            y*=p;
            return *this;
        }
        bool operator==(const vector &p)const
        {
            return !dcmp(x-p.x)&&!dcmp(y-p.y);
        }

        double length()//向量模 
        {
            return sqrt(x*x+y*y);
        }

        friend ostream& operator<<(ostream& out,vector& p)
        {
            out<<"("<<p.x<<","<<p.y<<")";
            return out;
        }
};
typedef vector point;

int cmp(const void *a,const void *b)
{
    point i=*(point*)a,j=*(point*)b;
    if(dcmp(i.x-j.x))return dcmp(i.x-j.x);
    return dcmp(i.y-j.y);
}

double angle(vector p1,vector p2)//两个向量夹角 
{
    if(p1.length()==0||p2.length()==0)
    return 0;
    return acos((p1*p2)/(p1.length()*p2.length()));
}

double angle2(vector p)//计算向量极角
{
    return atan2(p.y,p.x);
}

vector rotate(vector p,double rad)//逆时针旋转向量 
{
    return vector(p.x*cos(rad)-p.y*sin(rad),p.x*sin(rad)+p.y*cos(rad));
}

vector normal(vector p)//计算法向量
{
    if(!p.x&&!p.y)return p;
    return vector(-p.y/p.length(),p.x/p.length());
}

point getlineintersection(point p,vector v,point q,vector w)//计算直线交点
{
    if(!(v^w))return vector(0,0);
    vector u=p-q;
    double t=(w^u)/(v^w);
    return p+v*t; 
}

double distancetoline(point p,point a,point b)//计算点到直线的距离
{
    vector v1=b-a,v2=p-a;
    return fabs(v1^v2)/v1.length();
}

double distancetosegment(point p,point a,point b)//计算点到线段的距离
{
    if(a==b)return (p-a).length();
    vector v1=b-a,v2=p-a,v3=p-b;
    if(dcmp(v1*v2)<0)return v2.length();
    if(dcmp(v1*v3)>0)return v3.length();
    return fabs(v1^v2)/v1.length();
}

bool segacross(point p1,point p2,point q1,point q2)//判断线段p和q是否相交 
{
    if(dcmp((p1-q1)^(q2-q1))*dcmp((q1-p2)^(q2-q1))>0&&
       dcmp((q1-p1)^(p2-p1))*dcmp((p1-q2)^(p2-p1))>0)
    return true;
    return false;
}

bool onsegment(point p,point a,point b)//判断点是否在线段ab上
{
    return dcmp((a-p)*(b-p))<=0&&!dcmp((a-p)^(b-p));
}

int ispointinpolygon(point p,point *poly,int cnt)//判断点与多边形位置关系，顶点按逆时针序 
{
    int wn=0;
    for(int i=0;i<cnt;i++)
    {
        if(onsegment(p,poly[i],poly[(i+1)%cnt]))return -1;//边界;
        int k=dcmp((poly[(i+1)%cnt]-poly[i])^(p-poly[i]));
        int d1=dcmp(poly[i].y-p.y);
        int d2=dcmp(poly[(i+1)%cnt].y-p.y);
        if(k>0&&d1<=0&&d2>0)wn++;
        if(k<0&&d2<=0&&d1>0)wn--;
    }
    if(wn)return 1;//内部 
    return 0;//外部 
}

double polygonarea(point *p,int cnt)//计算多边形有向面积，顶点按逆时针序 
{
    double area=0;
    if(cnt<3)return 0;
    for(int i=1;i<cnt-1;i++)
    area+=(p[i]-p[0])^(p[i+1]-p[0]);
    return area/2;
}

int convexhull(point *p,int cnt,point *ch/*返回凸包顶点*/)//计算凸包，输入数组将被打乱，返回顶点个数 
{
    qsort(p,cnt,sizeof(point),cmp);
    int m=0;
    for(int i=0;i<cnt;i++)
    {
        while(m>1&&((ch[m-1]-ch[m-2])^(p[i]-ch[m-2]))<=0)m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=cnt-2;i>=0;i--)
    {
        while(m>k&&((ch[m-1]-ch[m-2])^(p[i]-ch[m-2]))<=0)m--;
        ch[m++]=p[i];
    }
    if(cnt>1)m--;
    return m;
}

int main()
{
    point a(1,1),b(3,0.5),c(2,1.5),d(3,1.5),e(5,1.5),f(1,2),g(3,2),h(3,3);
    point plg[]={a,b,c,d,e,f,g,h};
    point ch[10];
    cout<<convexhull(plg,8,ch)<<endl;
    for(int i=0;i<5;i++)
    cout<<ch[i]<<endl;
    //cout<<angle(p,b)<<endl;
    return 0;
}

线段树模板（双标记版）

#include<stdio.h>
#include<string.h>
#define INF (1<<30)
#define RIGHT (segt[cur].r)
#define LEFT (segt[cur].l)
#define SUM (segt[cur].sum)
#define MAX (segt[cur].max)
#define MIN (segt[cur].min)
#define RCHILD ((cur<<1)+1)
#define LCHILD (cur<<1)
#define TAG (segt[cur].tag)
#define TAG2 (segt[cur].tag2)
typedef struct
{
    int l, r;
    int sum, max, min;
    int tag, tag2;
} node;
node segt[10000];
int n, m, q;
int max(int a, int b)
{
    return a > b ? a : b;
}
int min(int a, int b)
{
    return a < b ? a : b;
}
void update(int cur)//更新线段树节点
{
    SUM = segt[LCHILD].sum + segt[RCHILD].sum;
    MAX = max(segt[LCHILD].max, segt[RCHILD].max);
    MIN = min(segt[LCHILD].min, segt[RCHILD].min);
}
void pushdown(int cur)//下推标记
{
    if(TAG)
    {
        segt[LCHILD].max += TAG;
        segt[LCHILD].min += TAG;
        segt[LCHILD].sum += TAG * (segt[LCHILD].r - segt[LCHILD].l + 1);
        segt[LCHILD].tag += TAG;
        segt[RCHILD].max += TAG;
        segt[RCHILD].min += TAG;
        segt[RCHILD].sum += TAG * (segt[RCHILD].r - segt[RCHILD].l + 1);
        segt[RCHILD].tag += TAG;
        TAG = 0;
    }
}
void pushdown2(int cur)//下推标记
{
    if(TAG2)
    {
        segt[LCHILD].max = TAG2;
        segt[LCHILD].min = TAG2;
        segt[LCHILD].sum = TAG2 * (segt[LCHILD].r - segt[LCHILD].l + 1);
        segt[LCHILD].tag2 = TAG2;
        segt[RCHILD].max = TAG2;
        segt[RCHILD].min = TAG2;
        segt[RCHILD].sum = TAG2 * (segt[RCHILD].r - segt[RCHILD].l + 1);
        segt[RCHILD].tag2 = TAG2;
        TAG2 = 0;
    }
}
void build(int cur, int l, int r) //建树
{
    LEFT = l;
    RIGHT = r;
    if(l >= r)return;
    build(LCHILD, l, (l + r) >> 1);
    build(RCHILD, ((l + r) >> 1) + 1, r);
}
void add(int cur, int l, int r, int val) //区间加值
{
    int mid = (LEFT + RIGHT) >> 1;
    if(LEFT >= l && RIGHT <= r)
    {
        TAG += val;
        SUM += val * (RIGHT - LEFT + 1);
        MIN += val;
        MAX += val;
        return;
    }
    pushdown(cur);
    if(l <= mid)add(LCHILD, l, r, val);
    if(r > mid)add(RCHILD, l, r, val);
    update(cur);
}
void set(int cur, int l, int r, int val) //区间设值
{
    int mid = (LEFT + RIGHT) >> 1;
    if(LEFT >= l && RIGHT <= r)
    {
        TAG2 = val;
        SUM = val * (RIGHT - LEFT + 1);
        MIN = val;
        MAX = val;
        return;
    }
    pushdown2(cur);
    if(l <= mid)set(LCHILD, l, r, val);
    if(r > mid)set(RCHILD, l, r, val);
    update(cur);
}

void modify(int cur, int x, int val) //单点修改
{
    int mid = (LEFT + RIGHT) >> 1;
    if(LEFT == x && RIGHT == x)
    {
        SUM = MAX = MIN = val;
        return;
    }
    if(x <= mid)modify(LCHILD, x, val);
    else if(x > mid)modify(RCHILD, x, val);
    update(cur);
}
int qsum(int cur, int l, int r) //区间和
{
    int mid = (LEFT + RIGHT) >> 1, rtn = 0;
    if(LEFT >= l && RIGHT <= r)
        return SUM;
    pushdown2(cur);
    if(l <= mid)rtn += qsum(LCHILD, l, r);
    if(r > mid)rtn += qsum(RCHILD, l, r);
    return rtn;
}
int qmax(int cur, int l, int r) //区间最大值
{
    int mid = (LEFT + RIGHT) >> 1, rtn = -INF;
    if(LEFT >= l && RIGHT <= r)
        return MAX;
    pushdown2(cur);
    if(l <= mid)rtn = max(rtn, qmax(LCHILD, l, r));
    if(r > mid)rtn = max(rtn, qmax(RCHILD, l, r));
    return rtn;
}
int qmin(int cur, int l, int r) //区间最小值
{
    int mid = (LEFT + RIGHT) >> 1, rtn = INF;
    if(LEFT >= l && RIGHT <= r)
        return MIN;
    pushdown2(cur);
    if(l <= mid)rtn = min(rtn, qmin(LCHILD, l, r));
    if(r > mid)rtn = min(rtn, qmin(RCHILD, l, r));
    return rtn;
}
int main()
{
    int i, j, l, r;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d%d%d", &n, &m, &q);
    build(1, 1, n);
    for(i = 1; i <= n; i++)
    {
        scanf("%d", &j);
        modify(1, i, j);
    }
    while(m--)
    {
        scanf("%d%d%d", &l, &r, &i);
        set(1, l, r, i);
    }
    while(q--)
    {
        scanf("%d%d", &l, &r);
        printf("%d %d %d\n", qsum(1, l, r), qmax(1, l, r), qmin(1, l, r));
    }
    return 0;
}